We propose an algorithm to compute the full output distribution of photons passing through linear optical interferometers. More precisely, given n photons at the input of an m-mode interferometer, the proposed algorithm computes the probabilities of all the $\binom{n + m - 1}{m - 1}$ possible output states in a linear time complexity of $O\left( {n\binom{n + m - 1}{m - 1}} \right)$, outperforming the naive method – computing one permanent for each state – by an exponential factor. The benchmarking has been carried out on a quantum machine learning use-case, to both illustrate the gain and give one possible application. Finally, as storing all the probabilities requires a memory space that is exponential in n and m, we discuss and give strong evidence that memory is far more limiting than the time for the computation of the full distribution.
We propose an algorithm to compute the full output distribution of photons passing through linear optical interferometers. More precisely, given n photons at the input of an m-mode interferometer, the proposed algorithm computes the probabilities of all the (m−1n+m−1) possible output states in a linear time complexity of O(n(m−1n+m−1)), outperforming the naive method – computing one permanent for each state – by an exponential factor. The benchmarking has been carried out on a quantum machine learning use-case, to both illustrate the gain and give one possible application. Finally, as storing all the probabilities requires a memory space that is exponential in n and m, we discuss and give strong evidence that memory is far more limiting than the time for the computation of the full distribution.
We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers. In particular, we define a model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number of photons in each mode. This model is not known or believed to be universal for quantum computation, and indeed, we discuss the prospects for realizing the model using current technology. On the other hand, we prove that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions. Our first result says that, if there exists a polynomial-time classical algorithm that samples from the same probability distribution as a linear-optical network, then P^#P=BPP^NP, and hence the polynomial hierarchy collapses to the third level. Unfortunately, this result assumes an extremely accurate simulation. Our main result suggests that even an approximate or noisy classical simulation would already imply a collapse of the polynomial hierarchy. For this, we need two unproven conjectures: the "Permanent-of-Gaussians Conjecture", which says that it is #P-hard to approximate the permanent of a matrix A of independent N(0,1) Gaussian entries, with high probability over A; and the "Permanent Anti-Concentration Conjecture", which says that |Per(A)|>=sqrt(n!)/poly(n) with high probability over A. We present evidence for these conjectures, both of which seem interesting even apart from our application. This paper does not assume knowledge of quantum optics. Indeed, part of its goal is to develop the beautiful theory of noninteracting bosons underlying our model, and its connection to the permanent function, in a self-contained way accessible to theoretical computer scientists.
Abstract Programmable linear optical interferometers are promising for classical and quantum applications. Their integrated design makes it possible to create more scalable and stable devices. To use them in practice, one has to reconstruct the whole device model taking the manufacturing errors into account. The inability to address individual interferometer elements complicates the reconstruction problem. A naive approach is to train the model via some complex optimization procedure. A faster optimization-free algorithm has been recently proposed (Bantysh et al 2023 Opt. Express 31 16729–42). However, it requires the full transfer matrix tomography while a more practical setup measures only the fields intensities at the interferometer output. In this paper, we propose the modification of the fast algorithm, which uses additional set of interferometer configurations in order to reconstruct the model in the case of intensity-only measurements. We show that it performs slightly worse than the original fast algorithm but it is more practical and still does not require intensive numerical optimization.
Multimode optical interferometers represent the most viable platforms for the successful implementation of several quantum information schemes that take advantage of optical processing. Examples range from quantum communication and sensing, to computation, including optical neural networks, optical reservoir computing, or simulation of complex physical systems. The realization of such routines requires high levels of control and tunability of the parameters that define the operations carried out by the device. This requirement becomes particularly crucial in light of recent technological improvements in integrated photonic technologies, which enable the implementation of progressively larger circuits embedding a considerable amount of tunable parameters. We formulate efficient procedures for the characterization of optical circuits in the presence of imperfections that typically occur in physical experiments, such as unbalanced losses and phase instabilities in the input and output collection stages. The algorithm aims at reconstructing the transfer matrix that represents the optical interferometer without making any strong assumptions about its internal structure and encoding. We show the viability of this approach in an experimentally relevant scenario, defined by a tunable integrated photonic circuit, and we demonstrate the effectiveness and robustness of our method. Our findings can find application in a wide range of optical setups, based on both bulk and integrated configurations.
For near-term quantum devices, an important challenge is to develop efficient methods to certify that noise levels are low enough to allow potentially useful applications to be carried out. We present such a method tailored to photonic quantum devices consisting of single photon sources coupled to linear optical circuits coupled to photon detectors. It uses the output statistics of BosonSampling experiments with input size n (n input photons in the ideal case). We propose a series of benchmark tests targetting two main sources of noise, namely photon loss and distinguishability. Our method results in a single-number metric, the Photonic Quality Factor, defined as the largest number of input photons for which the output statistics pass all tests. We provide strong evidence that passing all tests implies that our experiments are not efficiently classically simulable, by showing how several existing classical algorithms for efficiently simulating noisy BosonSampling fail the tests. Finally we show that BosonSampling experiments with average photon loss rate per mode scaling as o(1) and average fidelity of $ (1-o(\frac{1}{n^6}))^2$ between any two single photon states is sufficient to keep passing our tests. Unsurprisingly, our results highlight that scaling in a manner that avoids efficient classical simulability will at some point necessarily require error correction and mitigation.
Get PDF Email Share Share with Facebook Tweet This Post on reddit Share with LinkedIn Add to CiteULike Add to Mendeley Add to BibSonomy Get Citation Copy Citation Text J. P. Dowling, "Classical Computers Can Not Efficiently Simulate Multimode Linear Optical Interferometers with Arbitrary Fock-State Inputs," in The Rochester Conferences on Coherence and Quantum Optics and the Quantum Information and Measurement meeting, OSA Technical Digest (online) (Optica Publishing Group, 2013), paper W5B.1. Export Citation BibTex Endnote (RIS) HTML Plain Text Citation alert Save article
In his famous 1982 lecture, Nobel laureate Richard Feynman seeded the idea of quantum computation. He reasoned that the amount of classical information required to describe a quantum system scaled exponentially with its size, and thus could not be efficiently simulated by a classical computer. Indeed, a fairly modest system of 100 quantum bits would already require more information to describe than all the present data storage on Earth [1]. Given this, there would likely be computational tasks that achieve quantum supremacy—impossible to perform practically without the aid of a quantum information processor. In the 37 intervening years, these initial ideas have solidified, as the discovery of a string of quantum algorithms—from efficient factoring of large numbers to simulating chemical reactions—fueled a race for quantum supremacy. Yet, even theoretically, conclusively deciding—if quantum supremacy has been achieved—is non-trivial. Judging what problems can be efficiently solved by classical computers turns out to be exceedingly hard in itself. Take factoring, for instance. It is really classical intractable, or is it merely that we have not yet found an efficient classical means to factor? As we better understood how quantum computers process information, we also got better at finding classical methods to simulate them. This in turn has inspired new efficient classical algorithms in surprising situations [2]. Prof. Man-Hong Yung, associate professor at the Southern University of Science and Technology, and colleagues provided a beautiful illustration of such a discovery. Their work has been published in the July 2019 issue of National Science Review [3]. It considers a specialized type of linear optical quantum processor. The input and output are encoded within an array of optical modes by adjusting their initial photon number. Computation is achieved by interfering with these modes via a network of beam splitters, such that photons in one mode are transferred to another. Such processors have captured scientific attention due to their ability to perform a task known as boson sampling. When each mode is initialized with a single photon, the output statistics allows efficient evaluation of the matrix permanent—a computational problem with very strong evidence for being classically intractable [4]. This, coupled with their relative ease of engineering, made this specialized type of quantum processor an ideal holy grail for demonstrating quantum supremacy. Given this, one may expect that classical computers can say little about what such processors will output. After all, the number of paths that a photon can take to reach one mode from another scales exponentially with the size of the beam-splitter network. One may therefore assume that it would take exponential resources to track these paths to determine the probability of a photon moving from mode A to mode B. However, Yung and colleagues showed that a classical algorithm can efficiently estimate the transition probabilities—as long as one allows for additive error. This result represents a significant generalization of prior results by Scott Aaronson, which considers the case where there exists at most one photon in each mode [5]. In contrast, Yung's solution works regardless of the number of photons encoded in each mode. The result not only benefits the simulation of bosonic interference, but also has strong consequences in computing. Suppose that we use such specialized quantum processors to make binary decisions. That is, depending on input, we feed in particular distributions of photons—and then decide to take a particular action depending on whether the probability of seeing x photons in a particular output is above some threshold. In such contexts, a classical algorithm that estimates this probability up to the bounded additive error is sufficient for making identical decisions as the quantum processer itself. As such, Yung's algorithm enables a classical computer to be able to efficiently mimic the decisions of its specialized linear optical counterpart. This will no doubt have important ramifications in the present race for quantum supremacy. Much present effort is spent on demonstrating quantum supremacy through boson sampling, and the results here indicate that we will need to introduce more sophisticated quantum architectures if we wish to demonstrate such supremacy in making the right decisions.