We prove that a classical computer can efficiently sample from the photon-number probability distribution of a Gaussian state prepared by using an optical circuit that is shallow and local. Our work generalizes previous known results for qubits to the continuous-variable domain. The key to our proof is the observation that the adjacency matrices characterizing the Gaussian states generated by shallow and local circuits have small bandwidth. To exploit this structure, we devise fast algorithms to calculate loop hafnians of banded matrices. Since sampling from deep optical circuits with exponential-scaling photon loss is classically simulable, our results pose a challenge to the feasibility of demonstrating quantum supremacy on photonic platforms with local interactions.
We prove that a classical computer can efficiently sample from the photon-number probability distribution of a Gaussian state prepared by using an optical circuit that is shallow and local. Our work generalizes previous known results for qubits to the continuous-variable domain. The key to our proof is the observation that the adjacency matrices characterizing the Gaussian states generated by shallow and local circuits have small bandwidth. To exploit this structure, we devise fast algorithms to calculate loop hafnians of banded matrices. Since sampling from deep optical circuits with exponential-scaling photon loss is classically simulable, our results pose a challenge to the feasibility of demonstrating quantum supremacy on photonic platforms with local interactions.
To understand quantum optics experiments, we must perform calculations that consider the principal sources of noise, such as losses, spectral impurity, and partial distinguishability. In both discrete and continuous variable systems, these can be modeled as mixed Gaussian states over multiple modes. The modes are not all resolved by photon-number measurements and so require calculations on coarse-grained photon-number distributions. Existing methods can lead to a combinatorial explosion in the time complexity, making this task unfeasible for even moderately sized experiments of interest. We prove that the computation of this type of distribution can be done in exponential time, providing a combinatorial speed-up. We develop numerical techniques that allow us to determine coarse-grained photon number distributions of Gaussian states, as well as density matrix elements of heralded non-Gaussian states prepared in the presence of spectral impurity and partial distinguishability. These results offer significant speed-up and accuracy improvements to validation tests of both Fock and Gaussian boson samplers that rely on binned probability distributions. Moreover, they pave the way to a more efficient simulation of realistic photonic circuits, unlocking the ability to perform exact calculations at scales that were previously out of reach. In addition, our results, including loop Hafnian master theorems, may be of interest to the fields of combinatorics and graph theory.
Boson sampling is a fundamentally and practically important task that can be used to demonstrate quantum supremacy using noisy intermediate-scale quantum devices. In this Letter, we present classical sampling algorithms for single-photon and Gaussian input states that take advantage of a graph structure of a linear-optical circuit. The algorithms' complexity grows as so-called treewidth, which is closely related to the connectivity of a given linear-optical circuit. Using the algorithms, we study approximated simulations for local Haar-random linear-optical circuits. For equally spaced initial sources, we show that, when the circuit depth is less than the quadratic in the lattice spacing, the efficient simulation is possible with an exponentially small error. Notably, right after this depth, photons start to interfere each other and the algorithms' complexity becomes subexponential in the number of sources, implying that there is a sharp transition of its complexity. Finally, when a circuit is sufficiently deep enough for photons to typically propagate to all modes, the complexity becomes exponential as generic sampling algorithms. We numerically implement a likelihood test with a recent Gaussian boson sampling experiment and show that the treewidth-based algorithm with a limited treewidth renders a larger likelihood than the experimental data.
Boson sampling is a sampling task proven to be hard to simulate efficiently using classical computers under plausible assumptions, which makes it an appealing candidate for quantum supremacy. However, due to a large noise rate for near-term quantum devices, it is still unclear whether those noisy devices maintain the quantum advantage for much larger quantum systems. Since the noise rate typically grows with the circuit depth, an alternative is to find evidence of simulation hardness at the shallow-depth quantum circuit. To find the evidence, one way is to identify the minimum depth required for the average-case hardness of approximating output probabilities, which is considered a necessary condition for the state-of-the-art technique to prove the simulation hardness of boson sampling. In this work, we analyze the output probability distribution of shallow-depth boson sampling for Fock-states and Gaussian states, and examine the limitation of the average-case hardness argument at this shallow-depth regime for geometrically local architectures. We propose a shallow-depth linear optical circuit architecture that can overcome the problems associated with geometrically local architectures. Our numerical results suggest that this architecture demonstrates possibilities of average-case hardness properties in a shallow-depth regime, through its resemblance to the global Haar-random boson sampling circuit. This result implies that the corresponding architecture has the potential to be utilized for scalable quantum supremacy with its shallow-depth boson sampling.
Variational quantum algorithms are a leading approach to near-term quantum computing, but their scalability can be limited by barren plateaus and the sampling cost of resolving small changes in the loss landscape. Here, we study the trainability of passive linear-optical quantum circuits and introduce a framework based on the ratio of sample variance to circuit variance. This ratio determines the number of circuit samples required to resolve local loss differences and gradients to proportional accuracy. We apply this framework to photon-number observables and identify both trainable and non-trainable regimes. Supported by analytic results and a numerically observed polynomial decay of the circuit variance, we find that fixed-order photon-number polynomials require only polynomially many samples as the system size grows, whereas high-order polynomials and observables based on output probabilities generally require exponentially many samples. Within the trainable regime, we further identify classes of observables in which quantum estimation achieves a polynomial speed-up over multiple classical methods. Within this family, neural network observables provide one practical construction that allow measurement outcomes to be efficiently processed into the desired polynomial. These results establish photonic variational quantum computing as a promising platform for near-term applications.
We present a classical algorithm for approximating the expectation values of observables in linear optical circuits with arbitrary product input states, achieving additive-error accuracy. This result indicates that current applications of photonic systems aimed at demonstrating practical quantum advantage through expectation value estimation, such as photonic variational algorithms, may face challenges in attaining the computational advantage. It also implies the output probabilities of boson sampling with arbitrary product input states can be efficiently approximated by our method, so that boson sampling becomes efficiently simulable when its output probability distribution is polynomially sparse. We also develop an efficient classical algorithm for estimating transition amplitudes of arbitrary product states in linear optical circuits. This provides additive-error approximation algorithms for matrix functions associated with linear optical circuits, such as the (loop-)Hafnian, which are of independent interest. As an application, it solves the generalized molecular vibronic spectra problem [C. Oh et al., Nat. Phys. 20, 225 (2024)10.1038/s41567-023-02308-9], previously suggested as a candidate for practical quantum advantage. Finally, we extend our framework to near-Clifford circuits, enabling classical approximation of their expectation values.