PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum computing 40 years later

John Preskill

arXiv:2106.10522v3quant-ph

TL;DR

Large quantum systems are difficult to simulate classically because their state spaces grow exponentially, motivating Feynman’s quantum-computing proposal. The paper reviews the foundations, circuit model, hardware, simulation applications, and error-correction approaches. It concludes that quantum methods can achieve polynomial scaling for quantum dynamics, but practical use remains constrained by state preparation and the high overhead of fault tolerance.

  • Problem

    Classical computers cannot efficiently represent general large quantum states, creating a central challenge for simulating quantum systems.

  • Method

    The paper develops the quantum circuit model and reviews hardware, quantum simulation, energy estimation, and quantum error-correction approaches.

  • Results

    Quantum simulation can scale polynomially with physical-system size, whereas the best general-purpose classical algorithms scale exponentially.

  • Takeaways & Limitations

    Quantum computers offer a route to simulating quantum systems and computing their properties, subject to important implementation and preparation constraints.

  • Takeaways & Limitations

    Preparing an initial state with substantial ground-state overlap can be QMA-hard, while fault-tolerant quantum computing requires high qubit and gate overhead.

Abstract

from arXiv · show

Forty years ago, Richard Feynman proposed harnessing quantum physics to build a more powerful kind of computer. Realizing Feynman's vision is one of the grand challenges facing 21st century science and technology. In this article, we'll recall Feynman's contribution that launched the quest for a quantum computer, and assess where the field stands 40 years later.

1 Feynman and quantum computation

Feynman’s 1981 proposal argued that quantum computers could efficiently simulate quantum systems beyond classical computers’ reach, launching a new model of computation. The idea developed alongside formal quantum-computing theory and experimental proposals, while raising fundamental questions about computational power and physical realizability.

  • 1.1 Feynman’s 1981 talk: Feynman sought simulation resources proportional to the physical system’s space-time volume.This gave a concrete scaling goal for quantum simulation rather than merely proposing a qualitatively different computer.
  • 1.1 Feynman’s 1981 talk: In 1981, Feynman proposed quantum computers to simulate quantum systems that classical computers cannot efficiently represent.He argued that many-particle quantum states require too many variables for normal computers, motivating a different kind of machine.
  • 1.1 Feynman’s 1981 talk: The proposal challenged the classical universal-computer picture by suggesting that quantum systems may require quantum computation for efficient simulation.Feynman connected this challenge to the inability of classical devices to represent quantum-mechanical results and states succinctly.
  • 1.3 Related early ideas: Manin and Benioff pursued related quantum-computing ideas, respectively emphasizing classical simulation cost and quantum-mechanical models of computation.Benioff focused on whether quantum computation could operate without dissipation rather than on quantum complexity.
  • 1.2 Developing quantum computation: The field subsequently formalized quantum computation and investigated whether quantum computers could outperform classical computers beyond physics simulation.Deutsch formalized the model, while later work posed quantum speedup questions for problems unrelated to simulating physical systems.
  • 1.4 Imagining the future: Feynman’s broader insight was that quantum physics was not only a technological obstacle but also an opportunity to revise assumptions about physically realizable computation.He recognized that the extended Church–Turing thesis might need revision because nature is quantum mechanical.

2 Where we’re going and where we are

Quantum computing has produced striking demonstrations and may eventually transform quantum simulation, chemistry, and materials science, but current devices remain noisy, limited, and not yet broadly useful. The path to practical impact depends on improved control, fault tolerance, and applications whose value exceeds demonstration alone.

  • 2.1 How will quantum computers be used?: Quantum simulation remains the application most likely to have broad long-term impact, with possible benefits for pharmaceuticals, agriculture, and sustainable energy.The article contrasts this potential breadth with the nearer-term disruptive effect of factoring on electronic commerce.
  • 2.1 How will quantum computers be used?: Quantum computers do not generally provide efficient exact solutions to NP-hard optimization problems; Grover’s algorithm offers only a quadratic exhaustive-search speedup.The article distinguishes this limited speedup from the more substantial advantages expected for factoring and quantum-system simulation.
  • 2.2 The NISQ era unfolds: NISQ devices combine more than 50 controlled qubits with noise and no error correction, limiting their computational power.Current processors’ two-qubit gate error probability is slightly below 1%, and there is no convincing evidence that roughly 100-qubit, shallow circuits solve practical problems.
  • 2.3 Possible NISQ applications: Hybrid quantum/classical optimization is plausible, but it is not yet known whether it can outperform strong classical hardware and algorithms.The proposal relies heavily on classical processors while using a NISQ coprocessor for additional computational power.
  • 2.3 Possible NISQ applications: NISQ platforms may advance physics within five to ten years by preparing and studying exotic quantum states inaccessible in the laboratory.Analog simulators remain constrained by imperfect control and are best suited to robust, universal properties.
  • 2.4 From NISQ to FTQC: The gap from a few hundred physical qubits to hundreds of thousands or millions is expected to take substantial time, so transformative societal impact may be decades away.The article emphasizes that quantum technology remains at an early stage with competing approaches.

3 Quantum information

Quantum information differs from classical information through quantum states, including uncertainty, intrinsic randomness, and entanglement. Qubits can represent nonorthogonal states and exponentially complex descriptions, but measurement and state preparation constrain what quantum computers can access and efficiently create.

  • Quantum information is information encoded, stored, and processed in quantum states rather than classical physical states.
  • Quantum systems exhibit intrinsic randomness and measurement uncertainty because noncommuting observables can interfere and disturb subsequent measurements.
  • Entanglement allows a composite system to be completely specified while its individual parts remain incompletely characterized.
  • A qubit is a two-dimensional quantum-information unit represented by a normalized complex vector over orthogonal basis states |0⟩ and |1⟩.
  • 85.3% is the optimal success probability for distinguishing equally likely nonorthogonal states |0⟩ and |+⟩, unlike orthogonal basis states, which can be perfectly distinguished.
  • For 300 qubits, the state space has dimension 2^300 ≈ 10^90, yet one copy yields at most 300 classical bits through measurement.Holevo’s theorem limits classical information acquired from a single copy of an n-qubit state to n bits.
  • Although pairwise interactions can in principle create any entangled n-qubit state, approximating a typical state generally requires exponentially many interactions.The number of states approximable after T pairwise interactions grows exponentially in T, while the target state space is much larger.

4 What is a quantum computer?

A quantum computer is modeled as a system of qubits undergoing elementary unitary gates, with finite universal gate sets enabling efficient approximation of quantum computations. The model’s physical relevance remains conditional on assumptions about efficient simulation and scalable hardware.

  • Quantum circuit model: The computation arena is the Hilbert space H = C2n, decomposed into n qubits according to spatial locality.This tensor-product structure distinguishes the qubits as small subsystems within the larger space.
  • Quantum circuit model: Quantum gates are hardwired unitary transformations, each acting on a constant number of qubits and serving as quantum counterparts to classical elementary Boolean gates.Unitary operations describe the allowed evolution of a finite-dimensional quantum system.
  • Universal gates: One- and two-qubit gates suffice for universality, and two-qubit gates are preferred because they are generally easier to implement than gates acting on more qubits.A circuit of two-qubit gates can approximate any n-qubit unitary transformation as accurately as desired.
  • Universal gates: The finite gate alphabet is motivated by error correction: only gates compatible with the chosen code can be implemented efficiently and accurately enough for robust computation.Although physical transformations vary continuously, fault-tolerant operation favors a finite set of code-compatible gates.
  • Universal gates: The H, T, and CNOT gates form a universal set whose circuits can efficiently approximate other universal gate sets, with only modest overhead under the Solovay–Kitaev theorem.Approximating each simulated gate with error δ/T yields total error at most 2δ and overhead O(T polylog(T/δ)) for an efficient circuit.
  • Physical scope and hardware: The model’s physical scope is unsettled: efficient simulation is persuasive for finite-energy local quantum field theory, while black-hole physics may lie beyond its known reach.Scaling current platforms from tens to millions of physical qubits is also a major unresolved engineering challenge, with modular approaches still under development.

5 Simulating quantum dynamics

Quantum computers can efficiently simulate evolution generated by local Hamiltonians, addressing dynamics that are generally hard for classical computers. For geometrically local systems, the resulting quantum resources scale polynomially with system size and simulated time.

  • Local Hamiltonians: Local Hamiltonians describe interactions involving only a constant number of qubits, with geometrically local versions also restricting interactions to nearby qubits.A geometrically local Hamiltonian has O(n) terms when each qubit participates in only a constant number of interacting sets.
  • Simulation method: Quantum simulation approximates continuous evolution by dividing time into small steps and replacing each step with a product of local unitary gates.The per-step error must be controlled so accumulated error remains below the target accuracy δ.
  • Simulation method: Universal gate decompositions simulate the local gates, with Solovay–Kitaev adding a polylogarithmic overhead.The resulting circuit size is obtained by combining the number of time-step gates with the approximation cost of each gate.
  • Simulation method: For geometrically local Hamiltonians, only O(n) commutators contribute, yielding per-gate error O(∆^2h^2).Higher-order terms are suppressed by an additional factor of ∆h.
  • Resource scaling: Quantum resources for simulating a geometrically local system scale like the square of its spacetime volume up to a polylogarithmic factor.This is polynomial in the physical system size, whereas the best general-purpose classical algorithms scale exponentially.

6 Energy eigenvalues and eigenstates

Quantum phase estimation uses an efficiently implementable quantum Fourier transform to estimate eigenvalues of unitary time-evolution operators and Hamiltonians. The resulting energy estimates and eigenstate preparation are efficient under stated conditions, but obtaining a suitable initial state can remain hard.

  • Many-body Hamiltonian diagonalization seeks energy eigenvalues and eigenstate properties, but the 2^n × 2^n matrix can make the problem classically hard.
  • Quantum Fourier transform: The quantum Fourier transform uses O(m^2) gates, whereas the classical fast Fourier transform runs in O(N log N).Here N = 2^m, so N may be exponentially large in m.
  • Phase estimation: Phase estimation applies controlled powers of U and the QFT to estimate an eigenphase φ with accuracy δ ≈ 2^-m.The controlled evolution uses U up to approximately 2^m ≈ 1/δ times.
  • Hamiltonian eigenstates: For U = e^-iHT, phase estimation finds Hamiltonian eigenvalues to m-bit accuracy using a circuit whose size is polynomial in n.The construction interprets the phase-estimation control parameter as evolution time and uses efficient Hamiltonian simulation.
  • Hamiltonian eigenstates: Repeated measurements produce peaks at energy eigenvalues, with peak heights estimating the input state's squared overlaps with corresponding eigenstates.Measuring an eigenvalue can project the input state onto that eigenstate, enabling further property calculations.
  • Initial state preparation: Preparing an initial state with substantial ground-state overlap can be hard, including for local Hamiltonians where ground-state finding is QMA-hard.This limits the general practical use of otherwise efficient eigenvalue-estimation procedures.

7 Quantum error correction

Large-scale quantum computers remain unavailable because controlling quantum systems accurately is difficult, but quantum error correction offers a route to reliable storage and computation. Topological memories and the surface code protect logical information by distributing it nonlocally and can suppress logical errors below an accuracy threshold.

  • Challenges: Large-scale quantum computers do not yet exist because gate errors accumulate and environmental interactions cause decoherence.These effects can eventually produce computation-spoiling errors.
  • Quantum error correction: Quantum error-correcting codes redundantly encode logical information in many physical qubits and must correct both bit-flip and phase errors.Protecting a qubit therefore requires more than the bit-flip protection sufficient for a classical bit.
  • Quantum error correction: Reliable correction follows when no pair of correctable errors can distinguish the logical basis states, ensuring a recovery map for their linear combinations.The same conditions also preserve distinguishability in the dual basis.
  • Protected quantum memory: Topological quantum memories encode information in a two-dimensional medium where errors create anyons and nontrivial paths implement logical operations.The protected code space contains states with no anyons, while extended processes across the sample act on the encoded qubit.
  • Protected quantum memory: Monitoring diffusing anyons makes logical errors increasingly unlikely with system size, although unmonitored thermal excitations lack a growing energy barrier.The memory stores information for long times when temperature is small compared with the excitation gap.
  • Surface code: The surface code uses simple error diagnosis and tolerates relatively high gate error rates, making it a promising route to scalable fault-tolerant computation.For physical error rate ϵ below ϵ0 = 1/36 ≈ .028, its logical error probability decays exponentially with code distance d, apart from a possible polynomial prefactor.
  • Challenges: Practical fault tolerance still requires repeated syndrome measurements and substantial code distances, alongside major systems-engineering advances.Measurement errors require repeating syndrome measurements O(d) times, and very small logical error rates can demand large code distances.

8 Outlook

The outlook remains mixed: quantum computing may yield important applications in quantum physics and chemistry, while practical large-scale systems remain difficult to build. Near-term NISQ devices already support exploration of entangled many-body systems, hybrid algorithms, and methods for mitigating and correcting noise.

  • Outlook: Forty years after Feynman’s proposal, whether powerful quantum computers can be built appears answerable, but how and when remains unclear.The article says the answers to the other central questions are still far from clear.
  • Outlook: Improving physical entangling two-qubit gate error rates, currently around 1%, by several orders of magnitude would transform practical quantum-computing prospects.Progress so far has involved qubit design, control technology, fabrication methods, and materials.
  • Applications: Quantum computers are most clearly expected to advance science through applications in quantum physics and chemistry.The article identifies this as the most important clearly foreseeable application.
  • Near-term prospects: NISQ technologies enable exploration of highly entangled many-body systems and assessment of heuristic hybrid quantum/classical algorithms before fully scalable fault-tolerant machines arrive.They also advance noise mitigation and error-correction tools.
  • Broader impact: Quantum information concepts have also opened new research directions, including classifying quantum phases through long-range entanglement.The passage presents this as one of several broader advances across physics.

9 Memories of Feynman at Caltech

The author recalls Feynman as an intellectually wide-ranging, demanding, and vividly demonstrative Caltech colleague. These memories connect personal encounters, seminars, teaching, and research conversations with Feynman’s insistence on genuine understanding.

  • Colleagues: Preskill overlapped with Feynman at Caltech from August 1983 until Feynman’s death in February 1988.Their relationship as colleagues began soon after Preskill joined the faculty.
  • Colleagues: Feynman’s first hallway introduction to Preskill was characteristically disarming: he responded to “particle theory” by asking, “What group?”The exchange quickly established a memorable relationship.
  • Seminars: Caltech seminars featuring Feynman and Gell-Mann were famous for relentless questioning, though Preskill later found them less terrifying by playing the two against each other.Weinberg described Feynman as the more frightening of the two.
  • Influence: A childhood book about physics helped inspire Preskill’s eventual path to Caltech and later faculty relationship with Feynman.He later recognized that the book’s account drew on interviews with Caltech faculty.
  • Research conversations: Feynman and Preskill shared an interest in nonperturbative quantum chromodynamics, especially quark confinement, and often discussed it.Feynman valued the ideas themselves more than their literature references.
  • Colleagues: Feynman’s disagreements with Gell-Mann persisted into the 1980s, reflecting disputes over the parton model and the naming of quarks.The passage recounts both men’s accounts of how their relationship deteriorated.
  • Teaching: Feynman treated failure to explain spin and statistics at the freshman level as evidence that he did not truly understand it.He later developed a belt demonstration that Preskill continued using in teaching.
  • Later work: In his final years, Feynman returned enthusiastically to physics, pursuing QCD and integrable models through weekly meetings with students.He hoped integrable models might help address the soft part of QCD beyond perturbative methods.
Loading 2106.10522v3…