PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Sampling Problems, BosonSampling and Quantum Supremacy

A. P. Lund, Michael J. Bremner, T. C. Ralph

arXiv:1702.03061v1quant-ph

TL;DR

The paper addresses how quantum computation’s power can be demonstrated when universal, fault-tolerant machines may be impractical and classical simulation must be shown hard. It reviews complexity-based arguments for quantum sampling, focusing on BosonSampling and IQP Sampling. These intermediate models lower the proposed experimental requirements, although realistic errors and unresolved complexity conditions remain important boundaries.

  • Problem

    The exact computational power of quantum mechanics and the practicality of definitively demonstrating quantum supremacy remain only partially resolved.

  • Method

    The review synthesizes sampling-problem complexity arguments, emphasizing connections between quantum-circuit output probabilities and counting complexity, and surveys BosonSampling and IQP implementations.

  • Results

    BosonSampling and IQP provide intermediate quantum models for which reasonable output approximations are hard for classical computers under highly plausible conjectures.

  • Takeaways & Limitations

    Quantum sampling problems lower the barriers toward experimental demonstrations of quantum-algorithmic supremacy without requiring universal quantum operations.

  • Takeaways & Limitations

    Supremacy arguments for IQP still depend on unresolved mathematical statements connecting sufficiently hard output probabilities to sampling hardness.

Abstract

from arXiv · show

There is a large body of evidence for the potential of greater computational power using information carriers that are quantum mechanical over those governed by the laws of classical mechanics. But the question of the exact nature of the power contributed by quantum mechanics remains only partially answered. Furthermore, there exists doubt over the practicality of achieving a large enough quantum computation that definitively demonstrates quantum supremacy. Recently the study of computational problems that produce samples from probability distributions has added to both our understanding of the power of quantum algorithms and lowered the requirements for demonstration of fast quantum algorithms. The proposed quantum sampling problems do not require a quantum computer capable of universal operations and also permit physically realistic errors in their operation. This is an encouraging step towards an experimental demonstration of quantum algorithmic supremacy. In this paper, we will review sampling problems and the arguments that have been used to deduce when sampling problems are hard for classical computers to simulate. Two classes of quantum sampling problems that demonstrate the supremacy of quantum algorithms are BosonSampling and IQP Sampling. We will present the details of these classes and recent experimental progress towards demonstrating quantum supremacy in BosonSampling.

I. INTRODUCTION

The review situates quantum sampling as a route toward demonstrating quantum supremacy with less demanding physical requirements than universal quantum computation. It develops the theory of BosonSampling and related intermediate models while surveying BosonSampling experiments.

  • I. INTRODUCTION: Intermediate quantum-computing models have lowered the physical requirements for quantum speedup while strengthening arguments about classical simulation difficulty.The review connects this progress to the prospect of prototype quantum computers outperforming classical devices.
  • I. INTRODUCTION: BosonSampling produces samples from Fock-basis measurements of individually scattered bosons.The paper identifies 50 photons as sufficient for quantum supremacy using current classical-computation knowledge.
  • I. INTRODUCTION: Theoretical extensions include commuting quantum gates on qubits, known as IQP, with proposed demonstrations requiring systems of about 50 qubits.Experimental teams have pursued Aaronson and Arkhipov’s BosonSampling problem, while theorists generalized the arguments to IQP circuits.
  • I. INTRODUCTION: The review presents theoretical foundations for BosonSampling and its generalizations alongside recent experimental demonstrations of BosonSampling.Its theoretical focus is the connection between counting-problem complexity and sampling from quantum circuits.

II. COMPUTATIONAL COMPLEXITY AND QUANTUM SUPREMACY

Quantum supremacy requires arguments against all efficient classical algorithms, not merely comparisons with the best-known algorithms. Complexity theory supplies the framework for expressing this challenge and organizing relevant computational classes.

  • II. COMPUTATIONAL COMPLEXITY AND QUANTUM SUPREMACY: Complexity classes organize computational models by required algorithmic properties and output types.Table I distinguishes decision outputs, counting outputs, and generalized counting outputs allowing negative integers.
  • II. COMPUTATIONAL COMPLEXITY AND QUANTUM SUPREMACY: Shor’s factoring algorithm demonstrated a major quantum speedup, but factoring’s unknown complexity prevents it from by itself proving quantum supremacy.The best-known classical factoring method, the general number field sieve, is exponential time.
  • II. COMPUTATIONAL COMPLEXITY AND QUANTUM SUPREMACY: Quantum supremacy must be established against all possible classical algorithms, rather than only the best algorithms currently known.This distinguishes a proven separation from evidence based on an unresolved classical problem such as factoring.
  • II. COMPUTATIONAL COMPLEXITY AND QUANTUM SUPREMACY: The polynomial hierarchy is a nested oracle-based structure in which each level permits access to an oracle for problems from lower levels.The review notes that strict growth between levels is widely believed but unproven.

III. SAMPLING PROBLEMS

Sampling problems ask algorithms to generate random outputs from specified distributions, enabling quantum-versus-classical comparisons that connect circuit-output probabilities to complexity theory. The review explains these classes, their hardness arguments, and the approximation and error issues that shape supremacy claims.

  • III. SAMPLING PROBLEMS: Sampling problems output random numbers according to a specified probability distribution, and SampP and SampBQP denote efficient classical and bounded-error quantum sampling classes.A classical sampler transforms uniform random bits into nonuniform bits; SampBQP permits measurement of all output qubits.
  • III. SAMPLING PROBLEMS: Quantum circuits prepare |0⟩^n, apply a uniformly generated unitary circuit, and measure in the computational basis to produce an n-bit output.The output samples follow a distribution determined by the circuit C.
  • III. SAMPLING PROBLEMS: The central question is whether SampBQP strictly contains SampP; the review reports an almost provable separation between quantum and classical sampling complexity.This extends the broader observation that some quantum statistics cannot be recreated classically.
  • III. SAMPLING PROBLEMS: Output probabilities of suitable quantum circuits can be #P-hard, including for non-universal intermediate families such as IQP and BosonSampling.These hardness results are commonly obtained by showing universality under postselection.
  • III. SAMPLING PROBLEMS: For many circuit families, output-probability computation is GapP-complete, and multiplicative approximations remain GapP-complete.This supports hardness arguments under approximation rather than only exact computation.
  • III. SAMPLING PROBLEMS: Quantum implementations naturally provide additive rather than multiplicative approximations, creating the need for sampling-based arguments compatible with realistic errors.Total-variation closeness and specially chosen random circuits are used to connect additive sampling errors with multiplicative approximation arguments.

IV. BosonSampling PROBLEMS

BosonSampling evolves individual bosons through a linear optical network and samples all-mode Fock-basis outputs. Its probabilities depend on matrix permanents, supporting hardness arguments for exact and approximate sampling under stated conjectures and assumptions.

  • BosonSampling definition: Linear scattering networks mix annihilation operators through a unitary mode matrix u, realizable with beam splitters and phase shifters.The mode matrix u is distinct from the unitary operator acting on the Fock basis.
  • BosonSampling definition: BosonSampling evolves an n-boson Fock state through a linear network and outputs samples from an all-mode Fock-basis measurement.Output events are m-tuples of non-negative integers summing to n.
  • Output probabilities: Each output probability is proportional to the squared permanent of a submatrix A_S obtained from u by repeating rows according to the output event.The same unitary matrix ensures probabilities remain below 1 and the distribution is normalized.
  • Complexity: Exact BosonSampling is hard to simulate because permanents are #P-complete for 0–1 matrices and #P-hard to multiplicatively estimate for real matrices.The paper connects exact sampling from this distribution to a collapse of the polynomial hierarchy.
  • Approximate sampling: A 5-photon, 32-mode instance injects photons individually, applies a classically controlled scattering matrix, and detects every output in the Fock basis.The schematic summarizes the physical input, linear-interaction, and measurement stages.
  • Approximate sampling: Approximate-sampling hardness uses hidden random embeddings in sufficiently large Gaussian-distributed unitary networks, with total-variation error becoming additive estimation error.The argument relies on Gaussian permanent hardness and the Permanent of Gaussian Conjecture and Permanent Anti-Concentration Conjecture.

V. EXPERIMENTAL IMPLEMENTATIONS OF BosonSampling

Optical BosonSampling implementations use interferometers, single-photon inputs, and output detectors, but scalability is constrained by loss, imperfections, and network requirements. Experiments have validated small distributions directly and larger ones through efficient partial tests.

  • Optical implementation: Optical implementations inject single photons into a multipath interferometer and record output photon arrangements shot by shot.Under approximate-BosonSampling conditions, presence/absence detectors can replace photon-number-resolving detectors because multiple counts are suppressed.
  • Experimental limitations: Photon loss, mode mismatch, network errors, and imperfect state preparation and detection are the main experimental concerns.Post-selecting events where all photons survive can establish proof-of-principle devices but incurs exponential overhead and prevents scaling to large devices.
  • Experimental progress: A largest reported network used 3 photons in 5-, 7-, 9-, and 13-mode integrated optical interferometers with detectors at every output.The experiments used fixed on-chip interferometers, except for one partially tunable fibre-optic arrangement.
  • Experimental progress: 286 possible output events occurred in the 13-mode, 3-photon experiment, and measured probabilities agreed excellently with predictions across all chips.Direct characterization becomes intractable at larger scales because both probability computation and required data grow exponentially.
  • Experimental progress: Efficient partial validation can rule out uniform sampling or distinguishable-particle sampling using only small data subsets.These tests provide alternatives when complete distribution comparison is infeasible.
  • Scaling prospects: Medium-scale examples such as 50 bosons in 2,500 paths are argued to be classically intractable, while the practical challenge is low-loss, low-noise reconfigurable networking across hundreds to thousands of modes.Gaussian BosonSampling has also been demonstrated on a small scale using up to six independent squeezed-state sources.

VI. SAMPLING WITH THE CIRCUIT MODEL AND IQP

IQP circuits provide a circuit-model sampling problem whose classical hardness is tied to #P-hard output probabilities, anticoncentration, and average-case conjectures. The review also examines resource requirements, experimental constraints, and noise-related limitations.

  • IQP circuits: IQP circuits have the form C = H⊗nDH⊗n, with D diagonal and efficiently generated, and sampling measures H⊗nDH⊗n|0⟩⊗n in the computational basis.
  • Hardness arguments: Random IQP families based on Z, CZ, and CCZ gates have output probabilities that are #P-hard to compute in the worst case, including under multiplicative approximation.
  • Hardness arguments: Additive-error classical simulation would imply a collapse of the Polynomial Hierarchy when hidden subsets, anticoncentration, and sufficiently broad average-case #P-hardness conditions hold.
  • Experimental resources: Long-range interactions make random IQP circuits experimentally challenging, requiring up to O(n^2) or O(n^3) gates and potentially many SWAP gates on nearest-neighbour architectures.
  • Experimental resources: Sparse IQP sampling preserves anticoncentration and conjectured average-case #P-hardness with O(n log n) long-range gates or depth O(√n log n) in a universal 2d lattice architecture.
  • Experimental resources: For 2d lattices, amplitudes can be computed in O(2^t√n), while numerical studies suggest anticoncentration at depth O(√n), potentially enabling experiments near 50 qubits if errors remain low.
  • Limitations: Brickwork states offer constant depth but require stronger average-case conjectures and polynomially more qubits, while constant depolarizing noise can make anticoncentrated IQP circuits classically simulable to reasonable total variation distance.
  • Limitations: Definitive supremacy demonstrations require very high experimental precision, often motivating fault tolerance or error correction, although multiplicative-approximation hardness can persist under some errors.

VII. CONCLUSION

Quantum sampling problems lower the barriers to experimentally demonstrating quantum supremacy, while BosonSampling and IQP remain central intermediate models. The review points to continued theoretical and experimental work as bringing quantum devices closer to a definitive demonstration of quantum computational power.

  • VII. CONCLUSION: BosonSampling and IQP are the two main quantum sampling-problem classes used to demonstrate quantum supremacy.They correspond to intermediate optical and qubit-based quantum information-processing architectures.
  • VII. CONCLUSION: Even reasonable approximations to BosonSampling and IQP outputs are classically hard to compute under highly plausible conjectures.
  • VII. CONCLUSION: Future research must deepen understanding of these classes and address technological challenges in implementations that outperform the best-known classical algorithms.The cited directions include error detection and correction within intermediate models.
  • VII. CONCLUSION: Quantum sampling results have brought the field closer to constructing a device that definitively displays quantum mechanics’ computational power.

FUNDING

The listed research was supported by Australian Research Council programs, including a Centre of Excellence grant and a Future Fellowship.

  • FUNDING: APL and TCR received support from the Australian Research Council Centre of Excellence for Quantum Computation and Communications Technology.The funding was associated with Project No. CE110001027.
  • FUNDING: MJB received Australian Research Council support through the Future Fellowship scheme.The funding was associated with Project No. FT110101044.
Loading 1702.03061v1…