Source-linked AI summary
Sampling arbitrary photon-added or photon-subtracted squeezed states is in the same complexity class as boson sampling
Jonathan P. Olson, Kaushik P. Seshadreesan, Keith R. Motes, Peter P. Rohde, Jonathan P. Dowling
TL;DR
The paper asks whether non-Fock quantum states can yield sampling problems as hard as boson sampling. It shows that PASSV states with parity measurements implement the same sampling problem as Fock-state boson sampling, exactly and independently of squeezing.
Problem
The paper addresses whether quantum states of light other than Fock states can yield computationally hard sampling problems with linear optics.
Source: INTRODUCTION · p. 1Method
The authors map photon-added or -subtracted squeezed vacuum sampling with parity measurements to the same logical sampling problem as Fock-state boson sampling.
Source: INTRODUCTION · p. 2, Contrast with Fock State Boson Sampling · p. 4Results
PASSV sampling implements the same logical sampling problem as Fock-state boson sampling, exactly and independently of the squeezing parameter.
Source: INTRODUCTION · p. 2, Contrast with Fock State Boson Sampling · p. 4Takeaways & Limitations
PASSV sampling adds a non-Fock state family whose sampling problem has equal computational complexity to boson sampling across parameter regimes.
Source: DISCUSSION · p. 5Implementing parity measurements with photon-number-resolving detectors is experimentally harder than single-photon boson sampling, and large-squeezing noise sensitivity is not addressed.
Source: DISCUSSION · p. 5
Abstract
from arXiv · showhide
Boson sampling is a simple model for non-universal linear optics quantum computing using far fewer physical resources than universal schemes. An input state comprising vacuum and single photon states is fed through a Haar-random linear optics network and sampled at the output using coincidence photodetection. This problem is strongly believed to be classically hard to simulate. We show that an analogous procedure implements the same problem, using photon-added or -subtracted squeezed vacuum states (with arbitrary squeezing), where sampling at the output is performed via parity measurements. The equivalence is exact and independent of the squeezing parameter, and hence provides an entire class of new quantum states of light in the same complexity class as boson sampling.
INTRODUCTION
Full universal linear-optics quantum computing remains challenging with current technologies, motivating simpler sampling models. The paper asks whether non-Fock light states can yield sampling problems with boson sampling’s complexity and presents PASSV states as an example.
INTRODUCTION
- Universal LOQC remains challenging with current technologies, motivating simpler, more feasible approaches.Photons are relatively easy to prepare, manipulate, and measure, but full universal implementations remain impractical with current technology.Source: INTRODUCTION · p. 1
- Boson sampling uses passive linear optics for a sampling problem believed classically hard, while avoiding fast feedforward, optical quantum memory, and many optical elements.Its simpler setup and modest physical-resource requirements motivate interest in boson sampling as a possible route toward a post-classical quantum computer.Source: INTRODUCTION · p. 1
- The open question is whether non-Fock quantum states can yield hard sampling problems; earlier examples include two-mode squeezed vacuum and photon-added coherent states in the low-amplitude limit.Thermal inputs are efficiently simulatable, whereas some Gaussian states and generalized cat states have been shown to yield hard sampling problems.Source: INTRODUCTION · pp. 1–2
- The paper shows that photon-added or -subtracted squeezed vacuum states with parity measurements yield a problem of equal complexity to Fock-state boson sampling in all parameter regimes.The mapping is exact, so the authors state that the robustness result for approximate boson sampling also applies; experimental implementation is not the focus.Source: INTRODUCTION · p. 2
PASSV SAMPLING
The paper compares PASSV sampling with Fock-state boson sampling step by step. It establishes equivalence by showing that both implement the same logical matrix-permanent sampling problem.
PASSV SAMPLING
- The proof targets the same logical problem as AA boson sampling: sampling the output distribution associated with matrix permanents.This lets the authors apply existing complexity results rather than repeat AA’s lengthy complexity analysis, while requiring equivalence to be checked throughout the problem.Source: PASSV SAMPLING · p. 2
- Both models send m input modes through a passive linear interferometer and sample the joint output measurement distribution.The comparison classifies differences across input, evolution, output, and measurement, using photon-added states for consistency.Source: PASSV SAMPLING · p. 2
- The authors compare the models head-to-head before establishing that their shared sampling problem gives them the same computational complexity.The proof strategy is to track the differences at each stage rather than infer equivalence from the overall setup alone.Source: PASSV SAMPLING · p. 2
Contrast with Fock State Boson Sampling
Fock-state boson sampling uses single photons and vacuum inputs, while PASSV sampling uses photon-added or -subtracted squeezed vacuum and parity readout. The output parity identifies the same sampling configurations, yielding the same logical sampling problem independently of squeezing.
Contrast with Fock State Boson Sampling
- Fock-state boson sampling inputs n single photons into an m-mode interferometer with m − n vacuum modes, with m = Ω(n^2) under the bosonic birthday-paradox conjecture.A stronger m = Ω(n^6) requirement suffices without that conjecture.Source: Contrast with Fock State Boson Sampling · p. 2
- PASSV sampling instead inputs n photon-added squeezed-vacuum states and m − n squeezed-vacuum states, with equal but arbitrary squeezing across modes.Photon-subtracted states use annihilation operators in place of creation operators; the zero-squeezing case is excluded because annihilating vacuum gives zero.Source: Contrast with Fock State Boson Sampling · pp. 2, 4
- The PASSV network uses Haar-random real beamsplitters implementing an orthogonal matrix, whereas Fock-state sampling uses a Haar-random unitary matrix.The photon-subtracted output is associated with the transpose of the orthogonal matrix, which is also Haar-random and has the same computational complexity.Source: Contrast with Fock State Boson Sampling · pp. 3–4
- Fock-state output amplitudes are proportional to permanents of submatrices of the interferometer matrix, and the number of output configurations grows superexponentially with n.The output configuration S records the photon count in each mode.Source: Contrast with Fock State Boson Sampling · p. 3
- Squeezed vacuum contains only even photon-number terms, while applying a creation or annihilation operator yields odd photon-number terms in that mode.Thus parity distinguishes modes with an operator from modes without one.Source: Contrast with Fock State Boson Sampling · p. 4
- PASSV parity measurements recover the same sampling configurations and probability distribution as Fock-state boson sampling, independent of the squeezing parameter.The parity string uses values in {−1, 1}, rather than photon-number values in {0, 1}.Source: Contrast with Fock State Boson Sampling · p. 4
Complexity Concerns
PASSV sampling uses orthogonal matrices, so its complexity must be checked against Fock-state sampling with unitary matrices. The paper concludes the two models belong to the same complexity class.
Complexity Concerns
- Although the associated permanent complexity is necessary but not sufficient for hardness, the paper argues orthogonal matrices introduce no complexity gap versus unitary matrices.The passage notes that an efficient approximation for a matrix with even one negative entry would permit efficient computation of an exact {0, 1}-permanent.Source: Complexity Concerns · p. 5
- SU(m) is a subgroup of SO(2m), so orthogonal-matrix sampling is at least as hard as unitary-matrix sampling with a linear increase in modes.The passage also notes SO(2m) ⊂ SO(2m + 1), extending the result to odd mode counts.Source: Complexity Concerns · p. 5
- PASSV and Fock-state boson sampling are in the same complexity class, by reducing each model to the other through matrix-set inclusions at zero squeezing.The sampling output is independent of squeezing, so the proof may choose ξ = 0.Source: Complexity Concerns · p. 5
DISCUSSION
The discussion frames PASSV sampling as an exact, all-squeezing counterpart to Fock-state boson sampling and argues that computationally hard sampling is not unique to Fock states. It also identifies experimental costs and unresolved questions about other states and interferometer choices.
DISCUSSION
- The proposed mapping suggests using an invariant background signal and a measurement that distinguishes photon-added or -subtracted states, a strategy that may extend to other sampling problems.The authors identify more experimentally friendly state-and-measurement combinations as a future goal.Source: DISCUSSION · p. 5
- PASSV sampling has no squeezing bounds or approximations, while its parity measurement and state preparation may be experimentally harder than Fock-state boson sampling.At large squeezing, parameter error and noise sensitivity may add hurdles; these issues are not addressed here.Source: DISCUSSION · p. 5
- Whether unitary interferometers change PASSV sampling complexity remains open because the authors cannot establish a straightforward relation between output probabilities and submatrix permanents.At zero squeezing, PASSV sampling reduces to Fock-state sampling; a more complicated measurement might recover the same probabilities.Source: DISCUSSION · p. 5
- The direct mapping, together with results for photon-added coherent and generalized cat states, shows that many non-Fock states yield sampling problems of equal computational complexity.The authors leave full characterization of which optical systems and state classes are computationally hard to future research.Source: DISCUSSION · pp. 5–6
- The authors conclude that computational complexity is not unique to Fock states and appears ubiquitous among sampling quantum states of light.They note that PASSV may be experimentally more challenging than Fock-state boson sampling.Source: DISCUSSION · pp. 5–6