Cambridge University Press eBooks

Beyond Classical

Robert Hundt

Published Feb 28, 2022• 0 citations

Abstract

The term Beyond Classical is now the preferred term to describe computation that can be run efficiently on a quantum computer but would be intractable to run on a classical computer. A seminal paper by Google claimed to have reached this goal by computing a result in 200 seconds that a supercomputer would need 10,000 years to compute. Soon after publication, IBM claimed that the same computation could be done in just a few days on the Summit supercomputer. In this chapter, we analyze this disagreement. We discuss the proposition, implement and simulate the circuit, estimate simulation time for 53 qubits, and contrast Google’s claim against our implementation and IBM’s estimation result.

DOI: 10.1017/9781009099974.007

Related papers

Beyond Classical

Robert Hundt

This chapter serves as a bridge from the introductory material to the sections on quantum algorithms. We start by implementing a classical circuit using quantum gates and show that quantum computers are at least as capable as classical computers. Then we discuss the term “beyond classical,” which is now the preferred term to describe computation that can be run efficiently on a quantum computer but would be intractable to run on a classical computer. For this, we discuss in detail Google’s seminal quantum supremacy paper.

Cambridge University Press eBooksNov 20, 20250 citations

A Guide to Quantum Computers and the Development of Quantum Advantage

Siddharth Chander

Quantum advantage is when quantum computers can outperform classical computers.One of the first largescale demonstrations of quantum advantage was recently done by Google running random multi-qubit quantum circuits.While Google's quantum computer took 200 seconds, calculations show that the then-fastest classical supercomputer would have taken 10000 years.Since then, different groups have claimed quantum advantage through other quantum systems.This paper will cover why quantum computers can be faster than classical computers by covering the primary differences between classical computing and quantum computing.Then, we will investigate the Deutsch-Jozsa quantum algorithm and Google's claim of quantum advantage.We will review current research regarding "quantum advantage," tying these events to the use cases covered.Additionally, different quantum algorithms that are theoretically faster than any current quantum algorithms will be analyzed, and we will delve into why this is the case.The covered examples will show methods used to improve quantum computers to provide a significant time difference to achieve a quantum advantage.After that, we make predictions concerning two critical quantum hardware limitations.Finally, we will investigate what the future of quantum advantage entails and some future cases of quantum advantage.

International journal of high school researchJun 30, 20230 citations

Classical Simulation of Quantum Supremacy Circuits

Cupjin Huang, Fang Zhang, Michael Newman +10 more

It is believed that random quantum circuits are difficult to simulate classically. These have been used to demonstrate quantum supremacy: the execution of a computational task on a quantum computer that is infeasible for any classical computer. The task underlying the assertion of quantum supremacy by Arute et al. (Nature, 574, 505--510 (2019)) was initially estimated to require Summit, the world's most powerful supercomputer today, approximately 10,000 years. The same task was performed on the Sycamore quantum processor in only 200 seconds. In this work, we present a tensor network-based classical simulation algorithm. Using a Summit-comparable cluster, we estimate that our simulator can perform this task in less than 20 days. On moderately-sized instances, we reduce the runtime from years to minutes, running several times faster than Sycamore itself. These estimates are based on explicit simulations of parallel subtasks, and leave no room for hidden costs. The simulator's key ingredient is identifying and optimizing the "stem" of the computation: a sequence of pairwise tensor contractions that dominates the computational cost. This orders-of-magnitude reduction in classical simulation time, together with proposals for further significant improvements, indicates that achieving quantum supremacy may require a period of continuing quantum hardware developments without an unequivocal first demonstration.

arXiv:2005.06787May 14, 202076 citations

Beyond-Classical Computing Using Superconducting Quantum Processors

Joseph C. Bardin

The Google Quantum AI team's long-term goal is to realize a large-scale fault-tolerant quantum computer. Of the technologies available to implement the quantum processor at the core of such a system, solid-state superconducting circuits based on Josephson junctions (JJs) are among the strongest contenders. Recent demonstrations with this technology include computation beyond the capabilities of today's most powerful supercomputers [1] and execution of quantum error correction (QEC) codes that can detect and correct either bit or phase flip errors [2]. These exciting results were enabled by low-error-rate quantum processors with tens of qubits and the supporting infrastructure to run these devices. However, today's quantum computers still have orders of magnitude fewer qubits than is required for a useful fault-tolerant quantum computer; for this, an estimated million or more qubits will be needed and scaling-up today's technology to this extent is non-trivial. Here, we review the Google Quantum AI team's recent progress and future plans. Specifically, we describe our post-classical Sycamore quantum computer and discuss the Google Quantum AI roadmap to fault-tolerant quantum computing.

Digest of technical papers/Digest of technical papers - IEEE International Solid-State Circuits ConferenceFeb 20, 202221 citations

Quantum supremacy using a programmable superconducting processor

Frank Arute, Kunal Arya, Ryan Babbush +74 more

The promise of quantum computers is that certain computational tasks might be executed exponentially faster on a quantum processor than on a classical processor1. A fundamental challenge is to build a high-fidelity processor capable of running quantum algorithms in an exponentially large computational space. Here we report the use of a processor with programmable superconducting qubits2–7 to create quantum states on 53 qubits, corresponding to a computational state-space of dimension 253 (about 1016). Measurements from repeated experiments sample the resulting probability distribution, which we verify using classical simulations. Our Sycamore processor takes about 200 seconds to sample one instance of a quantum circuit a million times—our benchmarks currently indicate that the equivalent task for a state-of-the-art classical supercomputer would take approximately 10,000 years. This dramatic increase in speed compared to all known classical algorithms is an experimental realization of quantum supremacy8–14 for this specific computational task, heralding a much-anticipated computing paradigm. Quantum supremacy is demonstrated using a programmable superconducting processor known as Sycamore, taking approximately 200 seconds to sample one instance of a quantum circuit a million times, which would take a state-of-the-art supercomputer around ten thousand years to compute.

arXiv:1910.11333NatureOct 23, 20197,718 citations

Analysis and Implementation of Quantum Computing Algorithms

Caroline Fedele, Asai Asaithambi

In this research, we investigate the relationships between classical and quantum computing, and the superior time complexity and memory allocation proposed theoretically for quantum algorithms. This is accomplished by building quantum circuits to represent algorithms and test in a quantum computer simulation. Classical circuit components have been continually reducing in size to the point where they are now being impacted by quantum properties, resulting in the need to investigate quantum computing. The inherent parallelism of quantum computing also allows us to solve problems for which classical computers are inept. The class of intractable problems in computing where the solution can only be found through exhaustive search is where we observe quantum computing supremacy. It is important to explore and advance our knowledge of quantum computing so we are prepared for when it becomes a reality, and so that in the future our understanding of encryption is deepened and new quantum-proof methods can be developed. Although Google and IBM have developed physical quantum computers, there is still a large deficit in knowledge of how they may be utilized. There is also a gap between proposed superior quantum solutions and problems demonstrably solved using quantum algorithms. Among the problems classically considered intractable is one extremely relevant to cybersecurity, known as Shor’s algorithm, that being an efficient algorithm for integer factorization, breaks down our well-established methods of cryptography. The aim of this research is to show the differences and advantages of quantum computing, and to specifically demonstrate how we can use Shor’s algorithm in a quantum system.

Jan 1, 20200 citations