Sampling from probability distributions of quantum circuits is a fundamentally and practically important task which can be used to demonstrate quantum supremacy using noisy intermediate-scale quantum devices. In the present work, we examine classical simulability of sampling from the output photon-number distribution of linear-optical circuits composed of random beam splitters with equally distributed squeezed vacuum states and single-photon states input. We provide efficient classical algorithms to simulate linear-optical random circuits and show that the algorithms' error is exponentially small up to a depth less than quadratic in the distance between sources using a classical random walk behavior of random linear-optical circuits. Notably, the average-case depth allowing an efficient classical simulation is larger than the worst-case depth limit, which is linear in the distance. Besides, our results together with the hardness of boson sampling give a lower-bound on the depth for constituting global Haar-random unitary circuits.
Sampling from probability distributions of quantum circuits is a fundamentally and practically important task which can be used to demonstrate quantum supremacy using noisy intermediate-scale quantum devices. In the present work, we examine classical simulability of sampling from the output photon-number distribution of linear-optical circuits composed of random beam splitters with equally distributed squeezed vacuum states and single-photon states input. We provide efficient classical algorithms to simulate linear-optical random circuits and show that the algorithms' error is exponentially small up to a depth less than quadratic in the distance between sources using a classical random walk behavior of random linear-optical circuits. Notably, the average-case depth allowing an efficient classical simulation is larger than the worst-case depth limit, which is linear in the distance. Besides, our results together with the hardness of boson sampling give a lower-bound on the depth for constituting global Haar-random unitary circuits.
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.
We introduce a distributed classical simulation algorithm for general quantum circuits, and present numerical results for calculating the output probabilities of universal random circuits. We find that we can simulate more qubits to greater depth than previously reported using the cluster supported by the Data Infrastructure and Search Technology Division of the Alibaba Group. For example, computing a single amplitude of an 8×8 qubit circuit with depth 40 was previously beyond the reach of supercomputers. Our algorithm can compute this within 2 minutes using a small portion (≈ 14% of the nodes) of the cluster. Furthermore, by successfully simulating quantum supremacy circuits of size 9×9×40, $10\times 10\times 35 $, 11×11×31, and $12\times 12\times 27 $, we give evidence that noisy random circuits with realistic physical parameters may be simulated classically. This suggests that either harder circuits or error-correction may be vital for achieving quantum supremacy from random circuit sampling.
Boson sampling is a candidate for quantum protocols to truly realize the quantum computation advantage and to be used in advanced fields where complex computations are needed, such as quantum chemistry. However, this proposal is hard to achieve due to the existence of noise sources such as photon losses. In order to quantificationally analyze the influences of photon losses in optical networks, boson sampling is classically simulated based on the equivalent beam splitter mechanism, where the photon loss happening in optical units is equivalent to the photon transmission into the environmental paths through a virtual beam splitter. In our simulation, networks corresponding to random unitary matrices are made up, considering both the Reck structure and the Clements structure. The photon loss probability in an optical unit is well controlled by adjusting the parameters of the virtual beam splitter. Therefore, to simulate boson sampling with photon losses in optical networks is actually to simulate ideal boson sampling with more modes. It is found that when the photon loss probability is constant, boson sampling with Clements structures distinctly performs much better than that with Reck structures. Furthermore, the photon loss probability is also set to follow the normal distribution, which is thought to be closer to the situation in reality. It is found that when the mean value of photon loss probability is constant, for both network structures, errors of outputs become more obvious with the increase of standard deviation. It can be inferred that the increase of error rate can be explained by the network depth and the conclusion is suitable for larger-scale boson sampling. Finally, the number of output photons is taken into consideration, which is directly related to the classical computation complexity. It is found that with the photon loss probability, the ratio of output combinations without photon losses decreases sharply, implying that photon losses can obviously affect the quantum computation advantage of boson sampling. Our results indicate that photon losses can result in serious errors for boson sampling, even with a stable network structure such as that of Clements. This work is helpful for boson sampling experiments in reality and it is desired to develop a better protocol, for example, a well-designed network or excellent optical units, to well suppress photon losses.
Boson Sampling is a prominent candidate for the demonstration of quantum computational advantage but it remains unclear whether a large-scale boson sampler can find useful computational applications. The challenge is that to use a boson sampler to estimate, for example, a physical observable, it is necessary to coarse grain the outcome distribution, owing to the exponential size of the outcome space and the anti-concentration properties of the Boson Sampling distribution. In this work, we analyse the complexity of a specific type of coarse-graining of Boson Sampling distributions based on linear functions of the output photon occupation numbers, which we refer to as linear statistics. We present an efficient classical algorithm for approximating linear statistics of boson samplers within additive error for different kinds of input states, such as Fock states and squeezed states. This allows us to unify in the same framework recent results on efficient quantum-inspired classical algorithms for simulating molecular vibronic spectra, or efficient classical approximations of coarse-grained distributions based on detector binning. Additionally, we show how our algorithm can be used to classically evaluate a proposed one-way function based on Boson Sampling, while other proposals for cryptographic applications escape our classical simulation techniques. We leave open the question of classical simulability of non-linear statistics and connect it to the problem of computing transition amplitudes of linear-optical circuits with one layer of interactions.
Boson Sampling, a computational task believed to be classically hard to simulate, is expected to hold promise for demonstrating quantum computational advantage using near-term quantum devices. However, noise in experimental implementations poses a significant challenge, potentially rendering Boson Sampling classically simulable and compromising its classical intractability. Numerous studies have proposed classical algorithms that can efficiently simulate Boson Sampling under various noise models, particularly as noise rates increase with circuit depth. To address this challenge, we investigate the viability of achieving quantum computational advantage through Boson Sampling implemented with shallow-depth linear optical circuits. In particular, as the average-case hardness of estimating output probabilities of Boson Sampling is a crucial ingredient in demonstrating its classical intractability, we make progress on establishing the average-case hardness of Boson Sampling confined to logarithmic-depth regimes. We also obtain the average-case hardness for logarithmic-depth Fock-state Boson Sampling subject to lossy environments and for the logarithmic-depth Gaussian Boson Sampling. By providing complexity-theoretical backgrounds for the classical simulation hardness of logarithmic-depth Boson Sampling, we expect that our findings will mark a crucial step towards a more noise-tolerant demonstration of quantum advantage with shallow-depth Boson Sampling.