PaperlayerView exact revision on arXiv

Source-linked AI summary

The Computational Complexity of Linear Optics

Scott Aaronson, Alex Arkhipov

arXiv:1011.3245v1quant-phcs.CC

TL;DR

The paper addresses how to establish computational hardness for quantum systems whose simulation may be difficult but whose computational problems are unclear. It defines noninteracting-boson computation using linear-optical networks and proves hardness results for predicting its outcomes, including a finite-accuracy result conditional on factoring hardness. The analysis also identifies experimental and conjectural boundaries that remain open.

  • Problem

    Quantum systems may be hard to simulate classically, but it can be unclear how to interpret them as solving computational problems suitable for formal reductions.

  • Method

    The paper defines a noninteracting-boson model implemented by identical photons passing through beamsplitters and phaseshifters before their locations are measured, with equivalent mathematical formulations.

  • Results

    Predicting the results of a quantum-mechanical experiment to finite accuracy cannot be done in probabilistic polynomial time unless factoring integers can also be done efficiently, while approximating Per(X)^2 is #P-hard within any factor g ∈[1, poly(n)].

  • Takeaways & Limitations

    The results provide evidence that rudimentary linear-optical quantum systems can exhibit classically intractable computational behavior without relying on binary-encoded factoring as their computational task.

  • Takeaways & Limitations

    Finite experiments cannot decisively test the asymptotic Extended Church-Turing Thesis, and verifying BosonSampling may itself be infeasible when classical computation cannot solve it.

Abstract

from arXiv · show

We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers. In particular, we define a model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number of photons in each mode. This model is not known or believed to be universal for quantum computation, and indeed, we discuss the prospects for realizing the model using current technology. On the other hand, we prove that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions. Our first result says that, if there exists a polynomial-time classical algorithm that samples from the same probability distribution as a linear-optical network, then P^#P=BPP^NP, and hence the polynomial hierarchy collapses to the third level. Unfortunately, this result assumes an extremely accurate simulation. Our main result suggests that even an approximate or noisy classical simulation would already imply a collapse of the polynomial hierarchy. For this, we need two unproven conjectures: the "Permanent-of-Gaussians Conjecture", which says that it is #P-hard to approximate the permanent of a matrix A of independent N(0,1) Gaussian entries, with high probability over A; and the "Permanent Anti-Concentration Conjecture", which says that |Per(A)|>=sqrt(n!)/poly(n) with high probability over A. We present evidence for these conjectures, both of which seem interesting even apart from our application. This paper does not assume knowledge of quantum optics. Indeed, part of its goal is to develop the beautiful theory of noninteracting bosons underlying our model, and its connection to the permanent function, in a self-contained way accessible to theoretical computer scientists.

1 Introduction

The paper argues that even rudimentary linear-optical quantum systems provide evidence against efficient classical simulation. It defines BosonSampling and derives exact and conjecture-dependent approximate hardness results with polynomial-hierarchy consequences.

  • Motivation: Efficient classical prediction of quantum experiments is already difficult unless factoring is efficiently solvable classically, but Shor’s algorithm is technologically demanding.The paper motivates a simpler physical setting that could provide evidence against the Extended Church-Turing Thesis.
  • Model: The paper defines BosonSampling using identical photons passed through a linear-optical network and then measured for their output locations.The model uses beamsplitters and phaseshifters and is presented without requiring prior physics knowledge.
  • Exact case: Exact BosonSampling is not efficiently classically solvable unless P^#P = BPP^NP, which would collapse the polynomial hierarchy to the third level.The result also applies to classical oracle simulations and implies P^#P ⊆ BPP^NP.
  • Approximate case: Approximate BosonSampling is connected to approximating permanents, so an efficient approximate simulator would have major complexity consequences if the remaining gap is bridged.The argument depends on conjectures about Gaussian permanents and anti-concentration, and the paper proves related equivalences and hardness results.
  • Conjectures: The paper develops evidence for the Gaussian permanent conjectures, while showing that extending exact Gaussian hardness to approximate hardness requires going beyond Lipton’s interpolation technique.It also presents numerical and weaker theoretical evidence for anti-concentration.

2 Preliminaries

The preliminaries establish notation for Gaussian matrices, unitaries, norms, complexity classes, and sampling and search problems. They also introduce postselection classes and the equivalence between approximate sampling and search.

  • The paper uses G for the complex Gaussian distribution and G_n×n for n × n matrices with independent Gaussian entries.
  • U_m,n denotes m × n matrices with orthonormal columns, while H_m,n denotes the Haar measure over those matrices.
  • The operator norm ∥A∥ equals the largest singular value σ_max(A), and inputs are assumed to use polynomially bounded precision.
  • PostBPP and PostBQP condition acceptance on a separately defined success event, with PostBQP equal to PP.PostBPP is related to BPP_path, while PostBQP is characterized through the classical counting class PP.
  • Sampling problems concern generating distributions approximately, while search problems require outputting an element of a nonempty valid-solution set.The classes SampP, SampBQP, FBPP, and FBQP capture classical and quantum polynomial-time solvability in these settings; approximate sampling and search are equivalent under Theorem 12.

3 The Noninteracting-Boson Model of Computation

The paper formalizes computation with identical, noninteracting bosons, implemented as photons moving through linear-optical networks before final photon-number measurement. It develops equivalent physical and polynomial descriptions, connects amplitudes to permanents, and places BosonSampling between classical randomized and standard quantum computation.

  • Physical model: The model uses n identical photons in m modes, with photon occupations forming computational basis states whose total occupation remains n.Photons are initialized with one photon in each of the first n modes and are neither created nor destroyed during computation.
  • Physical model: The model has an exponentially large Fock-space Hilbert space, but unlike standard quantum-computing spaces it is not a tensor product of smaller Hilbert spaces.The basis consists of occupation-number tuples in Φm,n, the set of nonnegative m-tuples summing to n.
  • Physical model: Computation applies unitary transformations to the modes using beamsplitters and phaseshifters, then performs a nonadaptive measurement of photon numbers in every mode.Any m × m unitary can be decomposed into two-mode optical elements in polynomial size.
  • Polynomial model: A polynomial formulation represents states as multivariate polynomials, operations as unitary changes of variables, and measurements as sampling monomials weighted by coefficient magnitudes.The paper proves that this formulation is well-defined and equivalent to the physical linear-optics model.
  • Polynomial model: The Fock-space inner product equals expectation under complex Gaussian inputs, and this Gaussian interpretation is invariant under unitary transformations.The equivalence theorem preserves inner products and unitary transformations between quantum states and polynomials.
  • Computational consequences: The paper connects bosonic amplitudes to the permanent function and shows FBPP ⊆ BosonFPε = BosonFP ⊆ FBQP.BosonSampling search problems can therefore be simulated efficiently by standard quantum computers, while encompassing classical randomized computation.

4 Efficient Classical Simulation of Linear Optics Collapses PH

The paper proves that efficiently simulating exact BosonSampling would imply major complexity-class collapses, using permanent hardness and an alternative postselection argument. It then strengthens the result to fixed distributions and restricted boson computers.

  • 4.1 Basic Result: Exact BosonSampling enables approximation of |Per(X)|^2, which is #P-hard, through the connection between boson amplitudes and matrix permanents.The reduction establishes P^#P ⊆ BPP^NP^O for any exact BosonSampling oracle O.
  • 4.2 Alternate Proof Using KLM: An alternative proof uses adaptive linear optics, postselection, and PostBQP = PP to place postselected boson computation within postselected classical computation with a BosonSampling oracle.The proof invokes the Postselected KLM Theorem, PostBosonP = PostBQP, and derives the same complexity inclusion.
  • 4.1 Basic Result: Stockmeyer’s theorem provides multiplicative approximation for exponentially small acceptance probabilities of randomized polynomial-time algorithms using a BPP^NP machine.The result applies to sums of nonnegative real numbers but does not extend directly to quantum acceptance probabilities.
  • 4.1 Basic Result: The permanent-squared hardness proof reduces exact computation of the permanent of a Boolean matrix to multiplicative approximation of Per(X)^2 for real matrices.The reduction recursively perturbs matrix entries and uses adaptive oracle queries to identify the required value.
  • 4.1 Basic Result: A polynomial-time classical algorithm for exact BosonSampling would imply P^#P = BPP^NP and collapse the polynomial hierarchy to its third level.This is stated as both the main exact-sampling theorem and its corollary.
  • 4.3 Strengthening the Result: The strengthened result gives a fixed distribution D_n that boson computers can sample in polynomial time, while classical efficient sampling would imply P^#P = PH = BPP^NP.The distribution depends only on the input size, and coherent-state boson computers can sample from it efficiently.

5 Main Result

The paper’s main result connects approximate BosonSampling to permanent estimation through a Gaussian approximation for truncated Haar-random unitaries, yielding strong complexity consequences for classical simulation.

  • 5 Main Result: An n×n truncation of an m×m Haar-random unitary, scaled to mean 0 and variance 1, is close in variation distance to an n×n Gaussian matrix.The approximation holds when n is at most m^1/6, with m polynomial in n and 1/δ.
  • 5 Main Result: The proof bounds the variation distance by separately controlling the head distributions and the two tail probabilities.Matrices are partitioned according to whether their largest squared singular value is at most k or exceeds k.
  • 5 Main Result: The Gaussian approximation lets an approximate BosonSampling oracle estimate |Per(X)|^2 for Gaussian random matrices with high probability.The reduction combines the oracle with a hiding procedure and an approximate counting procedure.
  • 5 Main Result: If a fast classical algorithm approximately samples BosonSampling, then |GPE|^2 lies in FBPP^NP.The result is stated for any approximate BosonSampling oracle.
  • 5 Main Result: Under the paper’s conjectures, classical solvability of BosonSampling would imply consequences such as P^#P = BPP^NP and collapse of the polynomial hierarchy.The paper presents this as evidence against the Extended Church-Turing Thesis.

6 Experimental Prospects

The proposed experiment uses identical photons, a linear-optical network, and photon-number measurements to test permanent-based transition amplitudes, while remaining more experimentally accessible than universal quantum computation.

  • 6 Experimental Prospects: The target phenomenon generalizes the Hong-Ou-Mandel dip from two photons to three or more identical bosons.For two photons, destructive interference suppresses the outcome in which one photon occupies each output mode.
  • 6 Experimental Prospects: A finite experiment cannot settle asymptotic complexity claims, so its goal is to accumulate evidence against the Extended Church-Turing Thesis.The paper also leaves open hardness for fixed constant error δ and nontrivial error correction within the noninteracting-boson model.
  • 6 Experimental Prospects: The experiment prepares n identical photons, applies an m×m unitary using beamsplitters and phaseshifters, and measures photon counts in every mode.The resulting outcome is a basis state |S⟩ whose occupation numbers sum to n.
  • 6 Experimental Prospects: The measured probability of an outcome is computed from the squared permanent of a submatrix, divided by the factorials of its mode occupations.This is the n-boson transition-amplitude formula the experiment is intended to test.
  • 6 Experimental Prospects: The optical network can use O(mn) beamsplitters and phaseshifters arranged in O(n log m) layers.Parallelization exploits the fact that the initial state occupies only the first n modes.

7 Reducing GPE× to |GPE|2

The paper reduces multiplicative permanent estimation to estimating squared permanent magnitudes for Gaussian matrices, using anti-concentration and a noisy triangulation procedure.

  • 7 Reducing GPE× to |GPE|2: GPE× asks for multiplicative estimation of Per(X), whereas |GPE|^2± asks for additive estimation of |Per(X)|^2 for Gaussian matrices.The two problems use different targets and error formulations.
  • 7 Reducing GPE× to |GPE|2: The easy reduction from |GPE|^2± to GPE× is unconditional, while the reverse reduction requires the Permanent Anti-Concentration Conjecture.The paper’s main task in this section is the hard direction.
  • 7 Reducing GPE× to |GPE|2: Noisy triangulation recovers the permanent’s phase from squared-distance estimates to reference points, with stability supplied by Lemma 47.The reduction applies this geometric procedure inductively to estimate Per(X).
  • 7 Reducing GPE× to |GPE|2: The paper concludes that GPE× and |GPE|^2± are polynomial-time equivalent under the Permanent Anti-Concentration Conjecture.The final reconstruction obtains an approximation to Per(X)=re^iθ.
  • 7 Reducing GPE× to |GPE|2: The reverse reduction first estimates |Per(X)|^2, then reconstructs the phase Per(X)/|Per(X)| using oracle queries.The procedure uses 3N nonadaptive queries to the magnitude-estimation oracle.

8 The Distribution of Gaussian Permanents

This section studies the distribution of permanents of complex Gaussian matrices to support the Permanent Anti-Concentration Conjecture, which underpins stronger hardness conclusions. It presents numerical, determinant-based, and moment-based evidence, while proving only a weaker anti-concentration theorem for permanents.

  • Permanent Anti-Concentration Conjecture: The Permanent Anti-Concentration Conjecture says that |Per(X)| is at least n!/poly(n) for a 1−1/poly(n) fraction of Gaussian matrices.The conjecture concerns permanents of X drawn from the complex Gaussian ensemble and treats n! as the standard deviation.
  • Applications: The permanent conjecture has two applications: converting additive permanent estimation into multiplicative estimation and enabling estimation of the permanent itself from estimates of its squared magnitude.These applications strengthen the paper’s conclusions about Gaussian permanent estimation.
  • Evidence for the conjecture: Numerical evidence through n=10 is strongly consistent with the Permanent Anti-Concentration Conjecture.The observed bounds appear plausible for 0≤β<2, and perhaps also for β=2.
  • Determinant analogue: The determinant analogue is proved for all 0≤β<2, whereas extending the result to β=2 remains open.The determinant proof uses geometric properties and exact fractional and inverse moments, which are not known to extend to permanents.
  • Numerical distribution: For n=6, the normalized determinant and permanent squared magnitudes have equal expectation, E[Dn]=E[Pn]=1, while their density bends become steeper near zero as n increases.The figure does not establish whether either density diverges at the origin.
  • Permanent results: Theorem 54 proves weak anti-concentration: |Per(X)| has a non-negligible probability of being large enough for the paper’s application.This rules out the possibility that the permanent is almost always tiny and becomes large only on an exponentially small fraction of Gaussian matrices.

9 The Hardness of Gaussian Permanents

This section investigates the conjectured #P-hardness of approximating Gaussian permanents, using random self-reducibility and polynomial interpolation. It proves exact and sufficiently accurate average-case hardness results, but identifies a barrier to extending the reduction to the needed approximation regime.

  • Conjecture and motivation: The Permanent-of-Gaussians Conjecture—that multiplicatively estimating Per(X) for Gaussian X is #P-hard—is the central theoretical challenge left unresolved.If true, it would rule out polynomial-time multiplicative estimation under P^#P≠BPP.
  • Random self-reducibility: The reduction reconstructs q(t)=Per(X(t)) and evaluates q(0)=Per(X), transferring an oracle that succeeds on random Gaussian matrices to worst-case computation.The polynomial has degree at most n, and interpolation or error-correcting reconstruction recovers its value at zero.
  • Exact average-case hardness: Exact computation of Per(X) for Gaussian X is #P-hard on average, with success probability at least 3/4+δ for every δ≥1/poly(n).The proof adapts finite-field random self-reducibility: the permanent along a random line is a low-degree polynomial, reconstructed from random evaluations.
  • Squared-magnitude hardness: Computing |Per(X)|^2 for Gaussian X is also #P-hard, because it is a degree-2n polynomial and is #P-hard to compute in the worst case.The same random-self-reducibility proof extends from the permanent to its squared magnitude.
  • Approximation results: Theorem 62 establishes #P-hardness of approximating |Per(X)|^2 to additive error 2^-p(n,1/δ) with probability at least 3/4+δ over Gaussian X.This is an exponentially accurate additive-approximation result, not the full multiplicative Gaussian-permanent conjecture.
  • Approximation barrier: Assuming anti-concentration, ordinary polynomial interpolation cannot recover Per(X) at zero from approximate values at random points.Two low-degree polynomials can be indistinguishable at the sampled points yet behave differently at zero, creating the identified barrier.

10 Open Problems

The paper closes by listing open problems about proving its conjectures, improving linear-optical implementations, relating boson computation to other models, and establishing broader evidence for quantum computational advantage.

  • Linear-optical experiments: Experimental questions include reducing the number of optical modes and making the experiment fault-tolerant with effective error as small as 1/exp(n).The paper specifically asks whether fault tolerance is possible with fewer resources than universal quantum computation.
  • Conjectures: Proving the Permanent-of-Gaussians Conjecture remains the most obvious theoretical problem, including finding related average-case approximate-counting problems over the reals or complex numbers.The authors also ask whether one can at least show such a problem is not in BPP^NP.
  • Conjectures: Proving the Permanent Anti-Concentration Conjecture or otherwise understanding Gaussian permanent distributions is another central open problem.The conjecture concerns |Per(X)| exceeding a polynomially reduced scale with high probability.
  • Computational models: The authors ask how noninteracting-boson computation relates to models intermediate between BPP and BQP, including logarithmic-depth qubit circuits.They also seek analogous approximate-simulation hardness results for other quantum systems.
  • Complexity and verification: Open complexity questions concern whether approximate BosonSampling remains hard at fixed error, whether decision-problem analogues yield class collapses, and whether boson computers support efficiently verifiable proofs.These questions address approximation, decision complexity, verification, and interactive protocols.

12 Appendix: Positive Results for Simulation of Linear Optics

The appendix develops classical randomized and deterministic algorithms for selected properties of linear-optical networks, while clarifying why these results do not contradict BosonSampling hardness.

  • Photon-number marginals: A deterministic algorithm computes photon-number marginals for any k modes in n^O(k) time.It uses an exact algorithm for Per(V+I) when V has rank k, then solves (n+1)^k linear equations.
  • Photon-number marginals: These positive results remain consistent with hardness because full output probabilities or distributions require taking k≥n modes.Thus efficient computation is established for fixed-size marginals, not for the complete BosonSampling distribution.
  • Permanent approximation: The permanent estimator is unbiased because averaging the Ryser estimator over independent mean-zero, variance-one variables yields Per(V).The estimator is uniformly bounded by ||V||^n, enabling concentration bounds.
  • Permanent approximation: Gurvits’s randomized algorithm approximates Per(V) within additive error ±ε||V||^n with high probability.The estimator uses independent random sign vectors and Ryser’s identity.
  • Permanent approximation: For an n×n unitary U, Per(U) can be approximated within additive error ±ε in poly(n,1/ε) time.This is useful for amplitudes that may nevertheless be exponentially small for typical networks.

13 Appendix: The Bosonic Birthday Paradox

The appendix proves a bosonic analogue of the birthday paradox: with many more modes than n^2, Haar-random linear optics preserves collision-free outcomes with high probability.

  • Bosonic birthday paradox: When m≫n^2, n identical bosons initially occupying distinct modes will, with high probability, remain collision-free after a Haar-random m×m unitary.This matches the asymptotic collision behavior of classical particles despite bosonic bunching.
  • Proof method: The unitary pigeonhole principle bounds the probability of measuring a bad outcome by |B|/|G| when the input is uniformly distributed over a good set.The proof converts squared unitary amplitudes into a doubly stochastic transition matrix.
  • Proof method: Collision-free photon states form the good set G_m,n, while states containing repeated modes form the bad set B_m,n.The group of mode permutations acts transitively on the collision-free states, enabling the symmetry argument.
  • Bosonic birthday paradox: The Boson Birthday Bound applies the symmetry argument to the lifted unitary acting on the n-photon Hilbert space.The resulting bound controls the probability that a Haar-random unitary creates a collision.
Loading 1011.3245v1…