Source-linked AI summary
Quantum computing and the entanglement frontier
John Preskill
TL;DR
Quantum information science asks whether complex, entangled quantum systems can be controlled and used beyond classical computation. The paper discusses algorithmic separations, quantum simulation, and hardware-protection strategies. It concludes that quantum advantage is supported by several algorithmic examples, while practical scalability remains constrained by state-preparation difficulty, engineering challenges, and correlated noise.
Problem
The paper asks whether complex quantum systems can be controlled and whether their behavior or computation can exceed what classical systems can efficiently simulate.
Method
The paper examines feasible quantum states and local-Hamiltonian dynamics, quantum algorithms, and quantum-error-correction approaches for controlling and protecting quantum systems.
Results
Quantum algorithms exhibit known superpolynomial speedups for structured problems and polynomial speedups for tasks including search, while quantum error correction is scalable in principle below an accuracy threshold.
Takeaways & Limitations
Quantum advantage may be pursued through algorithms and quantum simulation, but reliable large-scale systems require protection against decoherence and suitable noise conditions.
Takeaways & Limitations
Ground-state preparation can be QMA-hard, and error correction may fail when noise acts collectively on many qubits.
Abstract
from arXiv · showhide
Quantum information science explores the frontier of highly complex quantum states, the "entanglement frontier." This study is motivated by the observation (widely believed but unproven) that classical systems cannot simulate highly entangled quantum systems efficiently, and we hope to hasten the day when well controlled quantum systems can perform tasks surpassing what can be done in the classical world. One way to achieve such "quantum supremacy" would be to run an algorithm on a quantum computer which solves a problem with a super-polynomial speedup relative to classical computers, but there may be other ways that can be achieved sooner, such as simulating exotic quantum states of strongly correlated matter. To operate a large scale quantum computer reliably we will need to overcome the debilitating effects of decoherence, which might be done using "standard" quantum hardware protected by quantum error-correcting codes, or by exploiting the nonabelian quantum statistics of anyons realized in solid state systems, or by combining both methods. Only by challenging the entanglement frontier will we learn whether Nature provides extravagant resources far beyond what the classical world would allow.
1. Introduction: toward quantum supremacy
Quantum information science probes whether complex quantum systems can be controlled and used to surpass classical computation. The field’s central challenge combines the promise of quantum advantage with the need to overcome decoherence.
- 1. Introduction: toward quantum supremacy: Quantum information science focuses on highly complex quantum states at the entanglement frontier.The paper frames this frontier as distinct from the short- and long-distance frontiers of particle physics and cosmology.
- 1. Introduction: toward quantum supremacy: Classical systems cannot in general simulate quantum systems efficiently, motivating controlled quantum systems with profoundly quantum behavior.The claim is presented as widely believed but not yet proved mathematically or experimentally.
- 1. Introduction: toward quantum supremacy: Quantum supremacy would mean performing tasks with controlled quantum systems beyond what ordinary digital computers can achieve.The paper links this goal to probing a previously unexplored physical regime.
- 1. Introduction: toward quantum supremacy: Decoherence is a formidable obstacle because unwanted environmental correlations make typical large quantum systems behave classically.Overcoming decoherence is presented as necessary for realizing controlled large-scale quantum systems.
- 1. Introduction: toward quantum supremacy: The field asks whether large-scale quantum systems are merely very difficult or potentially impossible to control, a question spanning engineering and physics.The answer would affect whether large quantum computers might be built after decades or perhaps centuries, if ever.
2. Quantum entanglement and the vastness of Hilbert space
Entanglement stores quantum information in correlations among many parts, making typical states difficult to describe or learn from locally. Yet physically feasible states occupy only a small, resource-limited region of Hilbert space and may still resist classical simulation.
- 2. Quantum entanglement and the vastness of Hilbert space: Entanglement is the characteristic correlation among quantum-system parts with no classical analog, with information distributed across their correlations.Measuring or reading a small subset of parts of a typical many-part state reveals negligible information about the whole state.
- 2. Quantum entanglement and the vastness of Hilbert space: A complete classical description of a highly complex quantum state would require a classical record of astronomical size.The paper uses the analogy of a quantum book whose information is not printed on individual pages.
- 2. Quantum entanglement and the vastness of Hilbert space: Although Hilbert space is vast, states that can be prepared with reasonable quantum resources occupy an exponentially small portion of it.The paper distinguishes physically relevant, preparable states from typical states whose preparation is infeasible.
- 2. Quantum entanglement and the vastness of Hilbert space: A feasible state can be generated from an uncorrelated product state using a polynomially bounded two-qubit circuit or local-Hamiltonian evolution for reasonable time.The same resource criterion is used to characterize feasible measurements.
- 2. Quantum entanglement and the vastness of Hilbert space: Feasible states and measurements may remain hard to simulate classically, which makes quantum computing potentially powerful.Their physical plausibility does not imply that they admit efficient classical descriptions.
3. Separating classical from quantum
Quantum algorithms provide evidence for separations between quantum and classical computational complexity, including superpolynomial speedups and more common polynomial improvements. These advantages appear structured rather than universal, while quantum simulation offers another important application.
- 3. Separating classical from quantum: Quantum algorithms such as Shor’s factoring and discrete-logarithm algorithms provide leading evidence for tasks beyond known efficient classical computation.They use a fast quantum Fourier transform to probe a function’s period.
- 3. Separating classical from quantum: Superpolynomial quantum speedups are known for structured problems including approximate evaluation of Jones polynomials and other topological invariants.Approximate Jones-polynomial evaluation is BQP-hard.
- 3. Separating classical from quantum: Quantum algorithms can estimate x†Mx for sparse linear systems in time scaling like a power of log N under efficient state-preparation and measurement conditions.The matrix is Hermitian, |b⟩ must be efficiently preparable, and M must be efficiently measurable; the problem is BQP-hard.
- 3. Separating classical from quantum: Polynomial speedups are more common, including exhaustive search in time scaling as the square root of classical time and quantum-walk-based Boolean-formula evaluation.The search speedup is attributed to probability being the square of a quantum amplitude.
- 3. Separating classical from quantum: Superpolynomial speedups appear limited to problems with special structure, while unstructured worst-case NP problems may receive no better than quadratic search speedups.The paper specifically names 3-SAT and the Traveling Salesman Problem as examples.
- 3. Separating classical from quantum: A natural quantum-computing application is simulating local-Hamiltonian evolution after preparing a reasonable state and before measuring a reasonable observable.The resulting findings may be difficult for classical computers to check.
4. Easiness and hardness
Quantum systems can be easy or hard to simulate classically depending on their structure, entanglement, and available operations. Several restricted models appear computationally powerful, while others become universal when specific resources are added.
- Special cases can be easy to simulate classically, providing guidance for seeking quantum supremacy.
- Circuits with only logarithmically many gates crossing each cut remain efficiently simulable because their states become only slightly entangled.
- For slightly entangled n-qubit states, linear in n measurements can suffice for tomography, followed by efficient classical stitching of constant-size segments.
- Gaussian optical dynamics and free fermions are classically easy to simulate, whereas optical nonlinearities, adaptive photon counting, or four-fermion interactions enable universal quantum computation.Adaptive fermion-number measurements do not add computational power, unlike the listed bosonic resources.
- The one-clean-qubit model can evaluate traces of exponentially large unitaries and support approximations to Jones polynomials and Turaev-Viro invariants.Its input consists of one pure qubit and many maximally mixed qubits.
- Commuting-gate circuits and nonadaptive linear optics may be hard to simulate classically despite being restricted models, but realistic photon loss could affect that hardness.The linear-optics route may require detecting coincidences involving about 30 photons to reach currently infeasible digital-simulation regimes.
5. Local Hamiltonians
Local-Hamiltonian dynamics can be simulated efficiently by quantum computers, enabling energy estimation and applications such as molecular ground-state calculations. However, preparing suitable ground-state inputs can itself be computationally hard.
- A local Hamiltonian is a sum of terms acting on a constant number of qubits, and sparse Hamiltonians also admit feasible simulation.
- Phase estimation measures energy by evolving an initial state under the Hamiltonian, Fourier-transforming an auxiliary register, and sampling the resulting frequency spectrum.
- An inverse-polynomial-overlap initial state enables ground-state energy measurement to inverse-polynomial accuracy in polynomial time.
- Preparing an initial state with substantial ground-state overlap can be very hard, while finding local-Hamiltonian ground states is QMA-hard.
- Quantum computers may efficiently simulate excited-state dynamics that are classically hard, including chemical reactions, quantum-field-theory scattering, and potentially quantum-gravity evolution.
6. Quantum error correction
Quantum error correction protects logical information by preserving distinguishability against both bit-flip and phase errors. Physical realizations include conventional codes and topologically ordered media, whose error mechanisms and scaling properties differ.
- Quantum error-correcting codes redundantly encode logical information across physical qubits and must correct both bit flips and phase errors.
- Correctability requires preserving distinguishability for computational and dual-basis states, which guarantees a recovery map for errors spanned by the error basis.
- A protected classical memory uses a ferromagnet, where majority readout corrects minority spin flips and domain-wall motion causes logical errors.
- A protected quantum memory can use two-dimensional Z2 topological order, encoding a qubit in a particle-free ground-state space and reading it through nonlocal string operators.
- The topological memory has long storage time at temperatures below its excitation gap, but size-independent passive protection; monitoring particle diffusion makes logical errors increasingly unlikely with size.
7. Scalable quantum computing
Quantum computing is scalable in principle when noise is sufficiently weak and suitably local or weakly correlated. Practical fault tolerance nevertheless requires cooling, parallel operations, engineering solutions, and control of collective noise.
- Below a critical accuracy threshold, noisy gates can simulate an ideal quantum circuit with reasonable overhead in gates and qubits.
- Two-dimensional short-range layouts favor topological codes that can be implemented with trapped ions, quantum-dot spins, or superconducting circuits.
- Scalable fault tolerance requires cooling to remove entropy introduced by noise, alongside substantial systems engineering.
- Parallel operations are necessary so noise can be controlled simultaneously in different parts of the computer.
- Scalability proofs apply to suitably local noise or sufficiently weak noise with correlations decaying rapidly in time and space.
- Quantum error correction may fail when noise acts collectively on many qubits, making correlation strength in actual devices a key practical concern.
8. Topological quantum computing
Topological quantum computing uses nonabelian anyons to protect and process quantum information, but its protection and computational scope impose important constraints. Large-scale implementations may therefore combine topological protection with standard quantum error correction.
- Nonabelian anyons offer an appealing route to fault-tolerant quantum computing through their exotic quantum statistics.
- Quantum information is protected when low temperatures suppress anyon-pair creation and large separations suppress unwanted tunneling interactions.Information processing uses anyon exchanges and their quantum statistics.
- Most anyon proposals require unprotected nontopological operations alongside braiding to achieve a universal gate set.Braiding alone is often nonuniversal, and some cases can be modeled by free-fermion Hamiltonians.
- Topological error rates are suppressed by the anyon-pair energy gap but do not improve with system size, so very large applications may need standard error correction.If topological protection yields very low gate error rates, the added coding overhead may be relatively modest.
- Known self-correcting quantum-memory models require four spatial dimensions, while a three-dimensional model has bounded storage time that declines beyond an optimal size.
9. Quantum computing vs. quantum simulation
Quantum simulation targets highly entangled matter and phenomena beyond accurate classical simulation. Universal digital computers offer adaptability and fault tolerance, whereas analog simulators provide customizable systems but have intrinsic limitations.
- Quantum computers could simulate highly entangled systems including antiferromagnets, exotic superconductors, biomolecules, nuclear matter, and spacetime near singularities.
- Digital and analog quantum simulation both seek quantum supremacy by revealing phenomena that classical systems cannot accurately simulate.The goal includes discovering new phenomena rather than merely testing existing theoretical predictions.
- Universal quantum computers can efficiently simulate any reasonable physical system, while analog simulators are customizable but intrinsically limited and not fault tolerant.For analog simulators, the role of simulation accuracy in classical hardness remains unclear.
10. Conclusions and questions
The paper frames quantum information science around whether controllable, highly entangled systems can surpass classical capabilities. Its concluding questions span near-term quantum simulation, scalable error correction, topological approaches, and self-correcting memory.
- Quantum supremacy and quantum error correction are presented as central goals and bases for achieving scalable quantum computing.
- Nature’s solutions to strongly correlated materials and complex molecules may suggest tasks beyond efficient classical simulation, although this remains unresolved.
- Quantum simulation with cold atoms and molecules is proposed as a possible path to quantum supremacy, subject to precise-control challenges.
- Systems of roughly 100 qubits may achieve super-classical tasks despite being too small for full quantum error correction or general-purpose computation.
- Near-term hardware experiments must clarify whether noise supports scalable fault tolerance and identify pitfalls arising as physical-qubit counts increase.
- The paper asks whether topological media and confirmed nonabelian anyons support physically realizable robust error-correcting codes.
- A central unresolved comparison is between topological quantum computing and standard qubits protected by quantum error-correcting codes.The distinction between these approaches may diminish as hardware advances.
- Self-correcting quantum memories remain an open question, including whether storage time can grow with system size while processing stays efficient and reliable.