Boundaries for quantum advantage with single photons and loop-based time-bin interferometers

Abstract

Loop-based boson samplers interfere photons in the time degree of freedom using a sequence of delay lines. Since they require few hardware components while also allowing for long-range entanglement, they are strong candidates for demonstrating quantum advantage beyond the reach of classical emulation. We propose a method to exploit this loop-based structure to more efficiently classically sample from such systems. Our algorithm exploits a causal-cone argument to decompose the circuit into smaller effective components that can each be simulated sequentially by calling a state vector simulator as a subroutine. To quantify the complexity of our approach, we develop a new lattice path formalism that allows us to efficiently characterize the state space that must be tracked during the simulation. In addition, we develop a heuristic method that allows us to predict the expected average and worst-case memory requirements of running these simulations. We use these methods to compare the simulation complexity of different families of loop-based interferometers, allowing us to quantify the potential for quantum advantage of single-photon Boson Sampling in loop-based architectures.

32 pages, 16 figures. This version: Cleveref configuration to correctly reference appendix sections

References in corpus (18)

• Boson sampling with 20 input photons in 60-mode interferometers at $10^{14}$ state spaces
• Scalable boson sampling with a single-photon device
• Scalable boson-sampling with time-bin encoding using a loop-based architecture
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• Efficient algorithm for boson sampling with partially distinguishable photons
• Partial indistinguishability theory for multi-photon experiments in multiport devices
• Simulating boson sampling in lossy architectures
• Classical algorithm for simulating experimental Gaussian boson sampling
• Classical simulation of boson sampling based on graph structure
• Tensor network states in time-bin quantum optics
• Strong Simulation of Linear Optical Processes
• Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
• Hardware requirements for realizing a quantum advantage with deterministic single-photon sources
• Certain properties and applications of shallow bosonic circuits
• Complexity-theoretic foundations of BosonSampling with a linear number of modes
• Laplace expansions and tree decompositions: A faster polytime algorithm for shallow nearest-neighbour Boson Sampling
• On computational complexity and average-case hardness of shallow-depth boson sampling
• Incoherent behavior of partially distinguishable photons