This page gives plain-language summaries of physics papers. We draw no link to Dost or to any other text; reading side by side is the reader's own work.
Experiment: measured. Theory: calculated or proved. Interpretation: its meaning is disputed. The labels are our own classification; a paper may have more than one nature.
Main question: How is a quantum computer defined, and how does it differ from a classical computer?
The mathematical model of the classical computer is the Turing machine. In 1985 Deutsch asked: if physics operates according to quantum mechanics, should not the most general model of computation also be based on quantum mechanics? The paper restates the Church-Turing hypothesis as a physical principle and defines a universal quantum computing machine.
On this page16. The Universal Quantum Computer · Deutsch 1985 — Quantum theory, the Churc · 17. Shor's Algorithm …
Proceedings of the Royal Society A 400, 97–117 theory
A paper that formulates the Church-Turing hypothesis as a physical principle and introduces the notions of the quantum Turing machine and the universal quantum computer.
The paper's starting point is this: the Church-Turing hypothesis says that everything that is "computable" can be computed by a Turing machine. Deutsch argues that there is a tacit physical claim underlying this hypothesis, and writes it out explicitly as a principle: "every finitely realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means."
The author notes that classical physics and the universal Turing machine do not satisfy this principle, because the former is continuous and the latter discrete. In contrast, he defines a class of computing machines that is a quantum generalization of Turing machines, and shows that quantum theory and the "universal quantum computer" are compatible with this principle.
These machines are said to have properties that no Turing machine can have. Among these is not the computation of non-recursive functions; but there is "quantum parallelism": certain probabilistic tasks can be performed faster by a universal quantum computer than by a classical restriction of it. The author argues that the intuitive explanation of this parallelism places a heavy burden on interpretations other than the Everett interpretation; this is a claim of interpretation and is disputed, and the paper presents no experimental result on this matter.
Finally the paper examines the ties of the theory of quantum computation with the rest of physics; it is suggested that quantum complexity theory gives a more reasonable definition of the "complexity" or "information" of a physical system than classical complexity theory.
The paper's two separate claims are evaluated separately: the definition of the quantum computing model and the computations this model performs differently from the classical one are a mathematical result; the interpretation concerning the Everett interpretation, on the other hand, is a view and is disputed.
Afterwards: In 1993 Bernstein and Vazirani took up this model again from the standpoint of complexity theory (topic 19 in this file).
17. Shor's Algorithm
Main question: Can large numbers be factored quickly?
Splitting a number into its prime factors takes a very long time for large numbers with known classical methods; widespread encryption schemes such as RSA rest on this difficulty. In 1994 Shor showed that on a hypothetical quantum computer the same task can be done in time polynomial in the number of digits of the number. This became one of the strongest reasons for interest in quantum computation.
Proc. 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), 124–134; tam sürüm: SIAM J. Comput. 26 (1997) 1484–1509, arXiv:quant-ph/9508027 theory
A paper giving polynomial-time algorithms on a quantum computer for factoring integers and computing discrete logarithms.
The paper's starting question is whether the computer is a universal computing device: can a classical computer simulate any physical computing device with at most a polynomial loss of time? Once quantum mechanics is taken into account, this is uncertain. The paper takes up two problems: factoring integers and finding the discrete logarithm. Both are considered hard on a classical computer and are the basis of many cryptographic proposals.
For both problems the author gives randomized algorithms on a hypothetical quantum computer that take a number of steps polynomial in the input size, that is, in the number of digits of the number. The 1994 proceedings paper presents these as "Las Vegas" algorithms and notes that they are the first examples of quantum code-breaking.
The core of the method can be summarized as follows: factoring is reduced to finding the period of a certain function. The quantum computer evaluates the function on many inputs in superposition; then the quantum Fourier transform makes readable the interference pattern that reveals the period. Once the period is found, the rest is ordinary classical computation. This summary describes the known structure of the algorithm, not the text of the paper.
The paper presents no hardware realization. Nor does it show that factoring on a classical computer is really hard; this hardness is generally assumed. What the paper shows is that these problems can be solved in polynomial time on a quantum computer.
The significance of the result is twofold: it shows that quantum computation can be exponentially faster than classical computation on a problem of widely assumed hardness; on the other hand, this speed can be obtained only with a sufficiently large, error-corrected quantum computer. The paper itself is not a proposal to build such a machine.
Afterwards: The full version of the paper was published in 1997 in the SIAM Journal on Computing. The error correction needed to run this algorithm at real sizes is the field of topic 15 in this file.
18. Grover's Algorithm
Main question: Can search problems be sped up?
To find a sought item in an unsorted list, there is no good classical way other than checking the items one by one. In 1996 Grover showed that a quantum computer can do this in a number of steps equal to the square root of the number of items. The speedup is not exponential as in Shor's algorithm but of square-root order; it is, however, valid for a general search problem.
Proc. 28th Annual ACM Symposium on Theory of Computing (STOC '96), 212–219 theory
A paper giving a quantum algorithm with O(√N) steps for search in an unsorted database.
The author explains the problem with a telephone directory example: N names are arranged at random and one wants to find the number of a given person. For a fifty percent probability of success, a classical algorithm (deterministic or probabilistic) must check at least N/2 names.
Because quantum systems can be in superposition, they can "check" many names at once. In the algorithm proposed in the paper the phases of various operations are carefully adjusted: successful computations reinforce one another, the others randomly cancel one another. As a result the sought number can be obtained in only O(√N) steps. That is, instead of the classical N/2, a number of steps of square-root order is needed. The known structure of the algorithm is the repetition of the same two operations: flipping the phase of the sought item and reflecting the amplitudes about the average of all items; in each round the amplitude of the sought item grows a little.
The paper also says that this algorithm is within a small constant factor of the fastest possible quantum algorithm. That is, a larger quantum speedup is not expected for a general (unstructured) search; the gain is limited to a square root.
The speedup is of square-root order; its practical meaning therefore depends on the size of the problem and the cost of quantum operations. The paper's abstract speaks only about the number of steps; it gives no device design.
The difference of this paper from Shor's algorithm is that the speedup does not rest on a special mathematical structure (periodicity), but in return is only a square root. Read together, these two show that the answer to the question of how much gain a quantum computer can provide, and on which problems, changes with the problem. The meaning of the square-root speedup can also be read this way: in a list of a million items classical search takes on the order of half a million steps, while quantum search takes on the order of a thousand steps; this is an example showing orders of magnitude, not a number in the paper.
Afterwards: The algorithm became a building block widely used in later work as a tool for general search and counting problems.
19. BQP: The Quantum Complexity Class
Main question: Exactly how powerful are quantum computers?
Complexity theory sorts problems into classes according to the resources needed to solve them. BQP is the class of problems that a quantum computer can solve efficiently (in polynomial time) with a small probability of error. Bernstein and Vazirani defined this class and examined its relation to classical classes.
Proc. 25th Annual ACM Symposium on Theory of Computing (STOC '93), 11–20; tam sürüm: SIAM J. Comput. 26 (1997) 1411–1473 theory
A paper that founded the complexity theory of quantum Turing machines and related the class BQP to classical classes.
The paper examines quantum computation from the standpoint of complexity theory. The first result is that, in Deutsch's quantum Turing machine model, an efficient universal quantum Turing machine exists. The authors note that this construction is much more complicated than its classical counterpart; they show that even simple principles such as looping, branching and composition are laborious in the quantum setting.
The second result concerns precision. How precisely must the transition amplitudes be specified? It is shown that O(log T) bits of precision suffice for a computation of T steps; thus it is argued that the quantum Turing machine can be regarded as a discrete, not an analog, model of computation.
The third result is the separation from the classical model. Assuming an oracle, a problem is found that the quantum Turing machine solves in polynomial time but the probabilistic classical Turing machine with bounded error (BPP) cannot solve in polynomial time. This is presented as the first formal proof, in the sense of modern complexity theory, that the quantum model goes beyond the Church-Turing thesis; it is a separation relative to an oracle, not without one.
Finally BQP is defined and the relation BPP ⊆ BQP ⊆ P^#P is shown. What this means is that showing mathematically, without an oracle, that quantum Turing machines are more powerful than classical probabilistic machines is not possible without a major advance in complexity theory.
The practical meaning of these results is this: whether BQP is strictly separated from the known classical classes remains an open question after this paper too. The authors state explicitly that a proof of this that required no oracle would mean a major advance in the theory. A note for the reader: BPP is the class of problems that a classical computer solves in polynomial time with randomness and a small probability of error; P^#P is a very powerful classical class, far beyond known efficient methods, so the upper bound on BQP is quite loose.
Afterwards: The full text was published in 1997 in the SIAM Journal on Computing. The summary read here is the abstract of the SIAM version; the text of the 1993 proceedings paper was not separately examined.
20. Quantum Supremacy
Main question: Has something that classical computers cannot do really been done?
Quantum supremacy is a quantum device solving a particular task so fast that it cannot be done in a reasonable time by the best known classical method. The task need not be useful. Google's 2019 Nature paper is the first experimental claim of this; in the same year IBM researchers argued that classical simulation might take much less time than claimed.
The Google paper claiming quantum supremacy by random circuit sampling on the 53-qubit superconducting Sycamore processor.
The paper is presented as an experimental test of the promise that quantum computers can perform certain tasks exponentially faster than classical computers. The difficulty is building a processor that works with high fidelity and can run quantum algorithms in a very large computational space.
The authors use a processor made of programmable superconducting qubits and produce quantum states on 53 qubits; the dimension of the corresponding computational space is 2^53, about 10^16. The task is to run a randomly chosen quantum circuit and sample the measurement results. The Sycamore processor takes about 200 seconds to sample one circuit instance a million times. The authors estimate, by their own benchmarks, that the same task would take about 10,000 years on the most advanced classical supercomputer. The resulting probability distribution is checked with classical simulations.
The authors describe this result as a dramatic speedup relative to all known classical algorithms and as the experimental realization of quantum supremacy for this particular computational task. Two points need attention. First, the task does not aim at a useful application; sampling the output of the quantum circuit is a benchmark on which speed is measured. Second, the 10,000-year figure is an estimate and may change as better algorithms are found on the classical side; indeed it later became a subject of debate.
The phrase that sets the scope of the paper's claim is "for this particular computational task." The authors report not that a useful problem has been solved but that a speed difference was observed on a particular sampling task. The paper also addresses the problem of verification: since computing the result classically at this scale is nearly impossible, correctness is tested on smaller circuits and simplified versions; this summary does not go into that detail.
Afterwards: In the same year Pednault and colleagues argued, with a simulation using secondary storage, that these circuits could be simulated on a supercomputer in a matter of days.
A response arguing that Sycamore circuits could be simulated within days on a classical supercomputer by using secondary storage.
An earlier work by the authors had shown that secondary storage (disks) can extend the range of quantum circuits that can be practically run in classical simulation. This paper improves those techniques and applies them to Sycamore circuits of 53 and 54 qubits. The paper appeared as a preprint shortly before the publication of Google's Nature paper.
The circuit pattern of interest (the entanglement pattern called ABCDCDAB) is of the kind that has proved hard to simulate classically with other approaches. According to the authors' analysis, on the Summit supercomputer at Oak Ridge National Laboratory these circuits can be simulated within a few days, up to arbitrary depth, with high fidelity and with all amplitudes given as output.
This is not an experiment but an analysis of computation. The "few days" estimate in the paper is a counter-estimate set against the "about 10,000 years" estimate in the Google paper. Since both estimates rest on the cost of the same task with different classical algorithms, the debate is not about an experimental result but about which classical method is best for this task and to what fidelity it must be computed.
This opposing work is cited as an example showing that claims of "quantum supremacy" are a threshold that can be shifted by the progress of classical algorithms. A note for the reader: circuit depth is the number of successive layers of gates in the quantum circuit; as depth grows, classical simulation generally becomes harder.
Afterwards: The debate continued in the following years with the development of classical simulation techniques; its details are not in this file.