Source-linked AI summary
Boson sampling with displaced single-photon Fock states versus single-photon-added coherent states---The quantum-classical divide and computational-complexity transitions in linear optics
Kaushik P. Seshadreesan, Jonathan P. Olson, Keith R. Motes, Peter P. Rohde, Jonathan P. Dowling
TL;DR
Boson sampling is a likely classically hard linear-optics sampling task, prompting the question of whether other light states can yield similar complexity. This paper studies displaced Fock states and photon-added coherent states with displaced photon-number detection. Displaced Fock-state sampling remains in the boson-sampling complexity class for all displacements, while photon-added coherent-state sampling transitions from likely hard at small amplitudes to classically simulatable at large amplitudes.
Problem
Method
The authors analyze displaced Fock states and photon-added coherent states in linear optics using displaced coincidence photon-number detection.
Source: §I · p. 2Results
Displaced Fock-state sampling is likely classically hard for all displacements, while photon-added coherent-state sampling is likely hard for |α|^2 ≤ 1/n and classically simulatable for |α|^2 ≥ n^2.
Source: §I · p. 2, §IV · p. 5Takeaways & Limitations
Abstract
from arXiv · showhide
Boson sampling is a specific quantum computation, which is likely hard to implement efficiently on a classical computer. The task is to sample the output photon number distribution of a linear optical interferometric network, which is fed with single-photon Fock state inputs. A question that has been asked is if the sampling problems associated with any other input quantum states of light (other than the Fock states) to a linear optical network and suitable output detection strategies are also of similar computational complexity as boson sampling. We consider the states that differ from the Fock states by a displacement operation, namely the displaced Fock states and the photon-added coherent states. It is easy to show that the sampling problem associated with displaced single-photon Fock states and a displaced photon number detection scheme is in the same complexity class as boson sampling for all values of displacement. On the other hand, we show that the sampling problem associated with single-photon-added coherent states and the same displaced photon number detection scheme demonstrates a computational complexity transition. It transitions from being just as hard as boson sampling when the input coherent amplitudes are sufficiently small, to a classically simulatable problem in the limit of large coherent amplitudes.
I. INTRODUCTION
Boson sampling offers a likely classically hard linear-optics task that is less demanding experimentally than full linear-optical quantum computation. This paper studies displaced Fock states and photon-added coherent states with displaced photon-number detection, finding distinct complexity behavior for the two inputs.
I. INTRODUCTION
- Boson sampling samples output photon-number distributions from single-photon inputs and is likely hard to simulate classically, while being less demanding to realize than LOQC.Experimental demonstrations, scalable implementations, certification methods, and realistic-implementation effects have also been studied [15] [16] [18] [20].Source: §I · p. 1
- Prior work found that photon-number sampling with Gaussian inputs can be as hard as boson sampling, while thermal-state sampling is classically simulatable and squeezed-vacuum sampling is likely hard in some cases [25].Photon-added or subtracted squeezed vacuum states and generalized cat states have also been shown to yield likely hard sampling problems [27].Source: §I · pp. 1–2
- The paper examines displaced Fock states and photon-added coherent states with displaced photon-number detection as alternatives to Fock-state inputs.Photon-added coherent states are photon-added displaced vacuum states.Source: §I · p. 2
- Displaced single-photon Fock-state sampling remains in boson sampling’s complexity class for any displacement, whereas photon-added coherent-state sampling transitions from likely hard at sufficiently small amplitudes to classically simulatable at large amplitudes.The paper derives an explicit bound on the sufficiently small coherent amplitudes.Source: §I · p. 2
- The paper reviews boson sampling, analyzes displaced Fock-state and photon-added coherent-state sampling, and concludes with a summary of the results.Source: §I · p. 2
II. AARONSON AND ARKHIPOV’S BOSON SAMPLING
Aaronson and Arkhipov’s boson-sampling setup sends single photons through a multimode linear-optical interferometer and samples output configurations. Its likely classical hardness is tied to permanent computation and complexity assumptions.
II. AARONSON AND ARKHIPOV’S BOSON SAMPLING
- The setup injects single-photon Fock states into the first n of m modes, with m = Ω(n^2), and vacuum into the remaining modes.Source: §II · p. 2
- An m-mode interferometer applies an m × m unitary using O(m^2) beamsplitters and phase-shifters, producing a superposition of n-photon output configurations.Source: §II · p. 2
- The output probabilities are sampled by coincidence photon-number detection, with post-selection on detecting all n photons to account for device inefficiencies.For m = Ω(n^2), the bosonic birthday paradox makes at most one photon per output mode likely, so on-off detectors suffice for large instances.Source: §II · p. 2
- Computing output amplitudes requires permanents of complex matrices, a #P-complete task with O(2^n n^2) runtime under Ryser’s algorithm; exact efficient classical sampling would imply polynomial-hierarchy collapse [30].The paper assumes exact and approximate boson sampling are classically hard, following Aaronson and Arkhipov.Source: §II · pp. 2–3
- Each output configuration S has amplitude γ_S proportional to the permanent of a submatrix selected by the input and output configurations.Source: §II · p. 2
III. SAMPLING DISPLACED FOCK STATES
Displacing each single-photon Fock-state input produces an output that is a displaced version of the ordinary boson-sampling state. Applying the inverse output displacement before photon-number detection recovers the boson-sampling problem.
III. SAMPLING DISPLACED FOCK STATES
- The output configuration S contains n photons in total, distributed across the modes.Source: §III · p. 3
- A linear-optical unitary transforms the input displacement amplitudes into new output amplitudes, while the remaining state is the ordinary boson-sampling output state.The derivation uses the invariance of vacuum under the unitary and the transformation of products of coherent states under linear optics.Source: §III · p. 3
- DSPFS sampling with inverse displacement followed by coincidence photon-number detection is in the same complexity class as Aaronson–Arkhipov boson sampling.The method counter-displaces output modes by amplitudes −β(j), which can be efficiently computed for any unitary; unbalanced homodyning can implement the displacement.Source: §III · p. 3
IV. SAMPLING PHOTON-ADDED COHERENT STATES
The section analyzes single-photon-added coherent states (SPACS), which differ from displaced single-photon Fock states in operator ordering. Photon-number sampling with SPACS inputs ranges from boson-sampling hardness at small coherent amplitudes to classical simulability at large amplitudes.
IV. SAMPLING PHOTON-ADDED COHERENT STATES
- SPACS and displaced single-photon Fock states differ by operator ordering, and SPACS Wigner-function negativity fades as |α| increases.The SPACS is heralded by mixing a coherent state and a single photon on a highly reflective beamsplitter and detecting vacuum in the transmitted mode.Source: §IV · pp. 3–4
- Photon-number detection outcomes with total photon number n select the AA boson-sampling term from the SPACS output superposition.Source: §IV · p. 5
- For |α|² ≤ 1/n, the AA component occurs with inverse-polynomial probability, so polynomially many measurements suffice to sample it.Source: §IV · p. 5
- When |α|² = 1/n², the probability P_n converges to one, reducing SPACS sampling to AA boson sampling without post-selection.Source: §IV · p. 5
- SPACS sampling is as hard as AA boson sampling for |α|² ≤ 1/n, but classically simulatable for |α|² ≥ n².In the large-amplitude regime, the output is always the m-mode vacuum.Source: §IV · p. 5
V. CONCLUSION
The conclusion contrasts two displacement-related inputs: DSPFS sampling remains likely classically hard for every displacement, while SPACS sampling changes complexity with coherent amplitude. For SPACS, the complexity transition is consistent with a conjecture linking computational complexity to Wigner-function negativity.
V. CONCLUSION
- SPACS Wigner-function negativity diminishes as coherent amplitude increases, alongside its transition from quantum to classical behavior.The conclusion says the complexity result is consistent with a conjecture relating computational complexity to Wigner-function negativity.Source: §V · pp. 5–6
- DSPFS sampling remains likely hard to simulate efficiently classically for all displacement values, while SPACS sampling transitions from likely hard at small amplitudes to classically easy at large amplitudes.The SPACS transition is also consistent with the conjecture that computational complexity relates to Wigner-function negativity.Source: §V · p. 6