arXiv:2609.18907
Logarithmic-depth quantum simulation of boson sampling
Changhun Oh
Abstract
We show that boson sampling with an arbitrary $m$-mode interferometer and $n\le m$ single-photon inputs can be simulated to inverse-polynomial total-variation error by a logarithmic-depth qubit circuit with polynomially many qubits. The circuit uses Clifford+$T$ gates, arbitrary qubit connectivity, and a single final measurement, and its family is logspace uniform. The key idea is to enlarge the optical system, decompose the resulting transformation into six quadratic shears, and distribute each mode over many submodes. This redistribution permits a fixed local occupation cutoff, after which local basis changes and parallel phase gates give the qubit circuit. Consequently, our result places boson sampling within shallow quantum computation.
AI Summary
The paper asks how much sequential qubit computation is needed to reproduce standard boson sampling with an arbitrary $m$-mode interferometer and $n\le m$ single-photon inputs. It constructs a sampler with total-variation error at most $\epsilon$, depth $O(\log(m/\epsilon))$, and width polynomial in $m$ and $1/\epsilon$. The circuit uses Clifford+$T$, arbitrary qubit connectivity, and only final measurement; its guarantee includes photon collisions and requires no postselection. For fixed inverse-polynomial accuracy, the family is logspace uniform, and its width can be $O(m^\alpha)$ for any fixed $\alpha>2$. Interferometer entries are supplied as finite-precision input bits rather than compiled into instance-specific circuits. The construction adds vacuum modes to obtain an equivalent $4m$-mode transformation that factors into six bounded quadratic shears. Each mode is then spread over $K$ submodes, allowing a fixed local occupation cutoff $s$. Local quadrature basis changes, coherent histogram counting, and parallel controlled phases implement the truncated shears. A dynamical truncation bound scales as $C_s(n+4m+2s+8)^{(s+3)/2}K^{-s/2}$, including temporary photon creation during the shears. Choosing $K=O(m^{1+3/s}\epsilon^{-2/s})$, and controlling coefficient rounding and gate synthesis, gives the stated resources. As a consequence, constant-gap promise decision problems defined by uniform $\mathrm{NC}^1$ predicates on the outputs lie in $\mathrm{BQNC}^1$. The result does not establish nonuniversality or minimum simulation depth. Geometrically local interactions, improved width and constants, and exact logarithmic-depth sampling remain open.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 18 pages, 1 figure