PaperlayerView exact revision on arXiv

Source-linked AI summary

Simulating boson sampling in lossy architectures

Raúl García-Patrón, Jelmer J. Renema, Valery Shchesnovich

arXiv:1712.10037v3quant-ph

TL;DR

The paper asks when photon loss makes boson-sampling experiments classically simulatable, an important question because losses are a major imperfection in multiphoton interference. It analyzes lossy linear-optics circuits and proves that exponential transmission decay permits efficient classical simulation, with the method determined by circuit depth. The authors conclude that single-photon linear-optics quantum-advantage experiments may require new platforms or ideas.

  • Problem

    Photon losses are a major imperfection in multiphoton interference, but their effect on the classical simulability of boson-sampling experiments is not well understood.

    Source: §1 · p. 2

  • Method

    The paper analyzes exponentially lossy linear-optics circuits using thermal-noise simulation for deep circuits and tensor networks for shallow circuits.

    Source: §1 · p. 2

  • Results

    For architectures with exponential transmission decay, circuits of depth D ≥ O(log M) admit polynomial-time thermal-noise simulation, while shallower circuits admit quasipolynomial-time tensor-network simulation.

    Source: §1 · p. 2, §8 · p. 16

  • Takeaways & Limitations

    The result suggests that single-photon linear-optics quantum-advantage experiments may need new theoretical ideas, technological developments, or platforms with very low algebraic transmission.

    Source: §8 · p. 16

    The thermal-noise bound is relatively loose and may be improved.

    Source: §3.1 · p. 6

Abstract

from arXiv · show

Photon losses are among the strongest imperfections affecting multi-photon interference. Despite their importance, little is known about their effect on boson sampling experiments. In this work we show that using classical computers, one can efficiently simulate multi-photon interference in all architectures that suffer from an exponential decay of the transmission with the depth of the circuit, such as integrated photonic circuits or optical fibers. We prove that either the depth of the circuit is large enough that it can be simulated by thermal noise with an algorithm running in polynomial time, or it is shallow enough that a tensor network simulation runs in quasi-polynomial time. This result suggests that in order to implement a quantum advantage experiment with single-photons and linear optics new experimental platforms may be needed.

1 Introduction

Boson sampling uses multiphoton interference in linear optics and was proposed as hard to simulate classically, but realistic loss raises questions about when that advantage persists. The paper argues that exponentially lossy architectures are classically simulatable, with thermal-noise or tensor-network methods depending on circuit depth.

1 Introduction

  • The introduction places boson sampling between universal linear-optics quantum computing and classical simulation: it removes feed-forward but is still considered hard to simulate classically.Boson sampling’s output statistics connect to the permanent of a unitary submatrix, a quantity described as #P-hard to compute.Source: §1 · p. 1
  • Earlier bounds required both losses and detector dark counts and were independent of system size, leaving loss alone unbounded by those results.The paper presents this gap as motivating a clearer account of when imperfections make boson sampling classically simulatable.Source: §1 · p. 2
  • For exponentially lossy architectures, circuits with D ≥ O(log M) admit polynomial-time thermal-noise simulation, while shallower circuits admit quasipolynomial-time tensor-network simulation.The authors state this result applies to architectures with exponential transmission decay, including many experimental platforms.Source: §1 · p. 2
  • Most demonstrated multi-photon-interference architectures have planar depth proportional to input size and constant loss per coupler, producing exponential transmission decay.The paper identifies integrated photonics and fiber-based platforms among those affected.Source: §1 · p. 2
  • The paper extends thermal-noise simulation to scattershot sampling, Gaussian measurements, and some architectures with non-exponential transmission decay, including free-space optics.The stated free-space example has quadratic transmission decay.Source: §1 · p. 2

2 Preliminaries

The preliminaries establish the boson-sampling model, describe how circuit loss can be represented, and collect trace-distance tools used in the main result.

2 Preliminaries

  • The M-mode Fock basis represents each mode by a photon-number state, with the occupation numbers collected into an integer vector.The section introduces this notation alongside its review of boson sampling and trace distance.Source: §2 · p. 3

2.1 The ideal boson sampling model

  • The ideal model sends N single photons through an M-mode linear-optics interferometer and measures output photon numbers; probabilities for bit-string outcomes connect to matrix permanents.A Haar-random unitary is required for the hardness proof discussed here, and circuit depth is treated as a free parameter.Source: §2.1 · p. 3

2.2 Modeling losses

  • A lossy circuit is represented by a contraction matrix A whose singular-value decomposition yields lossless transformations around parallel pure-loss channels.For uniform per-coupler transmission τ across D layers, transmission is μ = τ^D; the equivalent representation uses identical loss channels followed by U = VW.Source: §2.2 · pp. 3–4

2.3 Trace distance and its properties

  • Trace distance is invariant under unitaries, contracts under trace-preserving operations, and bounds the total-variation distance between measurement outcomes.For states diagonal in a common basis, trace distance equals the total-variation distance between their eigenvalue distributions.Source: §2.3 · p. 5

3 Main result

The main result gives two classical simulation regimes for lossy boson sampling: deep circuits are approximated by thermal noise, while shallow circuits can be simulated with tensor networks. For exponentially decaying transmission, the resulting algorithms run in polynomial or quasi-polynomial time, respectively.

3.1 Lossy boson sampling as thermal noise

  • At depth D̃, the output becomes ϵ-close to a thermal state; for N = 100, ϵ = 10^-6, and per-coupler loss x = 10^-3, D̃ = 9.205.The authors say the thermal-noise bound is relatively loose and requires transmission µ to decrease as N increases at fixed ϵ.Source: §3.1 · p. 6

3.2.1 Sufficient condition for efficient classical simulation of multi-photon interference

  • When D ≥ D*, a thermal-state sampling algorithm approximates the photon-counting statistics in polynomial time.The algorithm simulates thermal states using coherent-state mixtures, linear-optical evolution, and efficiently sampled Poisson photon counts.Source: §3.2.1 · pp. 6–7

3.2.2 Simulation of shallow boson sampling circuits using tensor networks

  • Tensor networks simulate an ideal circuit exactly in time O(M2(N + 1)8D), yielding quasi-polynomial time when depth scales logarithmically with M and equation (2) holds.The required local dimension is set by the total photon number in the circuit.Source: §3.2.2 · p. 7

3.2.3 Efficient simulation of architectures with exponential decaying transmission

  • The exponential-decay result combines the thermal-noise and tensor-network approaches to cover multi-photon interference in lossy architectures.For shallow uniform-loss circuits, surviving input photons are selected with probability µ = τ^D before tensor-network simulation.Source: §3.2.3 · p. 7
  • For exponentially decaying transmission, depth D ≥ D* permits polynomial-time simulation, while D ≤ D* permits quasi-polynomial-time simulation.The result concerns planar linear-optical circuits with transmission τ per layer and the stated relation between photons and modes.Source: §3.2.3 · p. 7

4 Additional results

The extensions cover algebraically decaying transmission and alternative boson-sampling proposals. They include a polynomial-time condition for algebraic losses and adapt the simulations to scattershot sampling and Gaussian measurements.

4.1 Algebraic decay of transmission

  • For algebraic losses, polynomial-time simulation applies at depths D ≥ D*; if γ/β < 2, sufficiently large M ensures this condition for depth D = M.The algebraic loss model uses length scale d and parameter β to describe the decrease in transmission.Source: §4.1 · p. 8

4.2 Generalization to alternative boson sampling proposals

  • Scattershot boson sampling adapts both algorithms by sampling valid heralding sequences and then simulating photons entering randomly selected input modes.The proposal uses two-mode squeezed vacuum states, with one half sent through the circuit and the other used to herald photon presence.Source: §4.2 · p. 8
  • For boson sampling with Gaussian measurements, the outcome statistics remain ϵ-close, and thermal-state simulation extends using techniques for Gaussian measurements on Gaussian states.Source: §4.2 · p. 8

5 Proof of Lemma 3

The proof replaces ideal exact-sampling oracles with efficient approximations for simulating photon counts from interfering thermal states. It bounds the combined approximation error and analyzes the costs of the three sampling steps.

5 Proof of Lemma 3

  • The ideal simulator samples a thermal state's coherent-state mixture, applies the interferometer, then samples Poisson photon counts; its exact Gaussian and Poisson oracles are idealizations.The realistic algorithm replaces these oracles with efficient approximations.Source: §5 · pp. 8–9

5.1 Error analysis

  • The total output-distribution error is bounded by the thermal-state, interferometer, and Poisson-sampling approximation errors, which are allocated to keep the result within ϵ.The proof uses the triangle inequality and contractivity of trace distance under trace-preserving maps.Source: §5.1 · pp. 9–10

5.2 Efficient coherent states constellations

  • A Gauss-Hermite coherent-state constellation approximates a single-mode thermal state, and a product of identical constellations extends the approximation to N modes.The constellation uses m roots of the mth Hermite polynomial, with weights providing exact integration for polynomials up to degree 2m − 1.Source: §5.2 · p. 10

5.3 Matrix multiplication

  • The coherent-state amplitude transformation β = Uα can be approximated within error ϵ in O(MN) operations, with polynomial-time overhead for arbitrarily small error.The induced coherent-state error is bounded by the matrix-multiplication error.Source: §5.3 · p. 11

5.4 Approximate Poisson sampling with Bernouilli trials

  • Each output-mode Poisson count is approximated by independent Bernoulli trials, with the trial count chosen using a trace-distance bound.The bound depends on the total input amplitude, which is controlled using unitarity and the coherent-state constellation's support.Source: §5.4 · p. 11

5.5 Algorithm scaling

  • For constant µ, the proof's cost scaling remains polynomial in the input photon number N, transmission M, and approximation quality ϵ.The scaling analysis sets m using N, ϵ, and µ; the stated regularity condition is ϵ/N ≤ 1 − δ for δ > 0.Source: §5.5 · p. 11

6 Proof of Lemma 5

Brute-force simulation requires representing a Hilbert-space coefficient tensor whose size grows exponentially when photon number and mode count increase proportionally. Tensor networks encode such states through smaller tensors and can be efficient when the state has strong locality.

6 Proof of Lemma 5

  • The brute-force state representation grows exponentially when photon number N and mode count M increase proportionally.Its memory and computational cost track the number of Hilbert-space coefficients.Source: §6 · p. 12
  • Tensor networks represent the state coefficients as a network of smaller tensors, enabling efficient encoding and manipulation when the state has a high degree of locality.Virtual indices contract while the M physical indices remain free.Source: §6 · p. 12

6.1 Matrix product states

The section introduces matrix product states as a tensor-network representation built through iterative singular-value decompositions. Its storage scales with the number of modes, local dimension, and squared maximum bond dimension.

6.1 Matrix product states

  • Iterative singular-value decomposition gives a matrix product state whose links carry Schmidt coefficients and ranks χk; its storage scales as O(M(d + 1)χ2).Here χ is the maximum link rank and d bounds the local physical dimension.Source: §6.1 · p. 12

6.2 Simulating ideal linear optics circuits

The section describes updating matrix product states under linear-optics gates and sampling from the resulting state. Single-mode gates update physical indices, while two-mode couplers use an operator decomposition and contractions of adjacent tensors.

6.2 Simulating ideal linear optics circuits

  • Linear-optics circuits are built from single-mode phase gates and two-mode couplers acting on adjacent modes, and the section updates an MPS before sampling its output.The MPS is represented as a one-dimensional graph of three-index tensors linked by contracted virtual indices.Source: §6.2 · p. 12, §6.1.1 · p. 12

6.1.1 Canonical form

  • Canonical form assigns diagonal Schmidt-coefficient matrices to MPS links, and the Schmidt decomposition provides the coefficients for bipartitions of the modes.The MPS can be transformed into this form.Source: §6.1.1 · p. 12, §6.2.1 · p. 13

6.2.1 One mode gates (phase rotation)

  • A phase rotation applies a diagonal gate with coefficients exp(iθni) to one mode's physical index, costing O((d + 1)χ2) without changing the MPS Schmidt coefficients.The gate contracts with the local tensor's physical index.Source: §6.2.1 · pp. 12–13

6.2.2 Two-mode couplers

  • The alternative two-mode update decomposes the coupler operator and contracts it with adjacent MPS tensors, improving on the prior O(χ3d3) scaling when χ exceeds d.The authors state this condition generally holds in most realistic simulations.Source: §6.2.2 · p. 14

6.2.3 Circuit simulation

  • Circuit simulation starts from vacuum product inputs and applies the MPS updates layer by layer; the bond dimension grows with circuit depth D.The supplied passage does not retain the displayed cost expressions.Source: §6.2.3 · pp. 14–15

6.2.4 Sampling from a matrix product state

  • Sequential conditional sampling contracts the MPS to obtain each mode's outcome probabilities and updates the state after each selected photon count; a sample costs O(M2(d + 1)8D+2) for D layers of couplers.The stated cost follows from a contraction bound of O(Mχ4(d + 1)2).Source: §6.2.4 · p. 15

6.3 Simulating ideal logarithmic depth circuits

Tensor-network simulation cost grows exponentially with circuit depth, while photon bunching requires a physical dimension set by the total photon number. When photon number scales with the number of modes, the resulting cost is quasipolynomial.

6.3 Simulating ideal logarithmic depth circuits

  • Photon bunching can make all N photons accumulate in one mode, so the simulation fixes the physical dimension to d = N.This differs from finite-spin simulations, where a constant physical dimension can support polynomial-time simulation at logarithmic depth.Source: §6.3 · p. 15
  • The tensor-network bond dimension scales exponentially with circuit depth.Source: §6.3 · p. 15
  • When N scales with M, contraction, storage, and sampling cost become quasipolynomial in system size.Source: §6.3 · p. 15

7 Generalization to non-uniform losses

Non-uniform losses can be decomposed into a uniform loss at the maximum transmission, followed by mode-specific residual losses. This decomposition extends the uniform-loss results to non-uniform interferometers and adapts the coherent-state and tensor-network simulations.

7 Generalization to non-uniform losses

  • Each mode's loss channel factors into a channel of transmission µ = max µ_i and a residual channel of transmission ˜µ_i = µ_i/µ.The common maximum-transmission channels commute with V, yielding the ordering of common loss, V, residual losses, and W.Source: §7 · p. 15, Figure 6 · p. 16

7.1 Generalizing Theorem 2

  • Because a quantum operation cannot increase trace distance, Theorem 2 extends to non-uniform losses by replacing uniform µ with µ = max µ_i.Source: §7.1 · p. 16

7.2 Generalizing lemma 3

  • For coherent-state inputs, the lossy transformation computes output amplitudes by β = Aα, followed by sampling from their Poisson distributions.Source: §7.2 · p. 16

7.3 Generalizing lemma 5

  • The tensor-network adaptation embeds losses as environmental couplings, producing a lossless circuit with M^2 modes and 6M^2 nearest-neighbor gates when D = M.This construction has less favorable cost but remains quasipolynomial; the authors note it is not optimal.Source: §7.3 · p. 16

8 Conclusion

For architectures with exponential transmission decay, the paper presents classical simulation algorithms for both deep and shallow circuits. It argues that current boson-sampling platforms therefore face a challenge in demonstrating quantum advantage, while identifying possible research directions and limits of the result.

8 Conclusion

  • For D ≥ O(log M), thermal-noise simulation runs in polynomial time; for D ≤ O(log M), tensor-network simulation runs in quasipolynomial time.The result concerns interferometers with exponential transmission decay, a feature of the vast majority of currently proposed architectures.Source: §8 · p. 16
  • Even under optimistic experimental parameters, quantum supremacy using the current boson-sampling hardness proof is out of reach.The authors suggest novel theory or technology, including platforms with very low algebraic transmission where their result would not apply.Source: §8 · p. 16
  • A shallow lattice architecture is proposed as a possible route to reduce circuit depth while maintaining complexity.The authors mention adapting a spin-lattice quenching proposal to quantum optics.Source: §8 · p. 17
  • Potentially restoring polynomial scaling for logarithmic-depth optical circuits would require an ε-approximate algorithm that truncates each mode to finite size.Photon bunching makes optical tensor-network simulation more involved than finite-spin counterparts.Source: §8 · p. 17
  • The authors conjecture that algorithms could interpolate between Clifford and Clifford simulation for ideal devices and fully efficient simulation for noisy devices.They describe this work as a first step and leave adaptation to other candidate platforms as an open question.Source: §8 · p. 17
Loading 1712.10037v3…