Quantum Advantage from Linear Optics

Quantum computing has promised advantages in a wide variety of problems, including simulating physical systems, optimisation problems and machine learning [1]. But these algorithms require large numbers of fault tolerant qubits, and are therefore infeasible on current hardware. So what can we do to highlight the power of quantum computing now? This is the question posed by the area of research known as Quantum Advantage: is there a problem which is easy to solve on a near-term quantum computer, yet intractable on a classical computer? Many problems have been proposed for this, including sampling from random quantum circuits, sampling from quantum circuits with a particular structure, and, the subject of this work, Boson Sampling [2].

Boson Sampling was originally proposed by Aaronson and Arkhipov in 2010, and is the problem of sampling from the output of a linear optical interferometer [3]. More concretely, if we have $n$ photons input into an $m$-mode interferometer implementing some unitary transformation $U \in SU(m)$, Boson Sampling is the task of sampling where the photons will come out. The first thing we can note about this model of quantum computing is that it is non-universal: photons are non-interacting, so without feed-forward or postselection in this model we cannot implement a two-qubit gate. However, photons can still interfere with each other in non-classical ways, most famously demonstrated by the Hong-Ou-Mandel dip [4]. So if we cannot perform universal quantum computation, can we still do something which is hard to simulate classically?

Aaronson and Arkhipov answered this affirmatively, showing that Boson Samplers can still demonstrate a quantum advantage [3]. To prove this, Aaronson and Arkhipov explained how the probability of seeing a given output from an $n$-photon $m$-mode interferometer is related to the permanent of an $n\times n$ submatrix of $U$. Computing the permanent of such a matrix is $\#P$-Hard, so an efficient algorithm for doing so would lead to significant consequences in Computational Complexity Theory, including a proof that $P=NP$. From this Aaronson and Arkhipov showed that, assuming various conjectures about matrix permanents hold and that $m = O(n^2)$, it is impossible for a classical computer to efficiently sample from this output distribution, or even from an $\epsilon$-close distribution in total variation distance.

In the years since, Boson Sampling has been a subject of interest among quantum photonics researchers. Early demonstrations ranged from 3-6 photons [5,6,7,8,9,10], with more recent work showing up to 14 output photons [11]. A particularly exciting development came in 2020, where a group led by Lu and Pan demonstrated a variant known as Gaussian Boson Sampling with up to 76 detected photons, which is claimed to be beyond the limit of what is classically simulable [12].

Classical Simulations from Photonic Imperfections

But even if Boson Sampling becomes classically intractable for sufficiently large $m$ and $n$, an important question is at what point will we actually see an advantage? If we want a fair race, we need to compare the best Boson Sampling experiments to the best classical algorithms. This has led to the development of several classical algorithms for Boson Sampling [13,14,15,16,17,18,19,20].

One particular detail that these classical algorithms take advantage of is that Boson Sampling experiments suffer from practical imperfections. Such imperfections include:

• • loss, where a photon is generated at the start of the interferometer but not detected at the end

• • and distinguishability, where photons are generated at different wavelengths, polarisations, or even at different times, and as a result no longer interfere with each other.

In extreme cases, either of these imperfections can lead to a point where the experiment becomes trivial to classically simulate. If there is significant loss, one can simply simulate a vastly reduced number of photons. And if all the photons are fully distinguishable from each other, each photon can be simulated individually.

A particular classical algorithm which takes advantage of these imperfections was first proposed by Renema et al. [15], and subsequently improved in work by Renema, Shchesnovich and García-Patrón [16]. Here, these imperfections are characterised by parameters $\xi$ and $\eta$, which denote the probability of an individual photon being indistinguishable from other photons, and the probability of an individual photon not being lost, respectively. With knowledge of these parameters, one can simulate such an experiment up to accuracy $\epsilon$ by instead simulating a Boson Sampling experiment with $k$ ideal photons and $n-k$ fully distinguishable photons. The time complexity for this algorithm is exponential in terms of $k$, where $k$ is dependent on $\xi$, $\eta$, and $\epsilon$. Crucially, $k$ is not dependent on $m$ or $n$, so the algorithm’s runtime will only increase at most polynomially as the size of our interferometer increases. As a result, it is not sufficient to simply make larger interferometers with more photons; if we don’t work on improving these imperfections as well, then we will not achieve a quantum advantage.

How to Spot the Difference

So what can we do to ensure that we have an advantage over these classical algorithms? Can the classical algorithms produce an output which is the same as our imperfect experiment, or at least close enough that to us they look identical? Or is there a way to distinguish an actual Boson Sampling experiment from a classical simulation?

This is the question posed in recent work by Shchesnovich [21], which showed that in fact it is possible to distinguish the output of a Boson Sampling experiment from that of the algorithm by Renema, Shchesnovich and García-Patrón [16]. To do this, we select a subset of $L$ output modes. Let us use $P_L$ to denote the probability of detecting zero photons in these modes in an experiment, and $\tilde{P_L}$ for the corresponding probability in a classical simulation. Shchesnovich showed that there is a lower bound for the difference between these two probabilities $|P_L-\tilde{P_L}| \geq \Delta$.

This gives us a way of determining if a collection of samples is from a classical simulation or a real Boson Sampling experiment. First, we use the samples to estimate the probability of seeing zero photons in these $L$ modes, $P_L$. Next, we use a classical computer to estimate the values $\tilde{P_L}$ and $\Delta$. And finally, we check if the inequality $|P_L-\tilde{P_L}| \geq \Delta$ holds: if it does then our samples are likely from an actual experiment, and if it doesn’t then they are probably from a classical simulation. Shchesnovich showed that for fixed distinguishability and loss, and for a classical simulator with fixed $k$, the number of samples required depends only on $n/m$, the ratio of photons to modes. Since $m=O(n^2)$ for Boson Sampling, this ratio can be upper-bounded by some constant value. Therefore, as the number of photons and the size of our interferometer increases, the number of samples and computation time required to distinguish an experiment’s output from a classical simulation only increases polynomially.

Conclusion and Outlook

We have now reached the era in quantum computing where we are seeing the first claims of a quantum device performing a computation which is classically infeasible. As we see these claims appear, it is important that we ask just how well classical computers can perform, and if there are ways that quantum computers can stand out. The recent result by Shchesnovich works towards answering the latter of these questions, giving a metric by which Boson Sampling experiments can distinguish themselves from classical simulations.

There are still interesting questions to explore here. Shchesnovich considered a particular family of classical algorithms, but there are other classical algorithms for simulating Boson Sampling for which the method discussed above might not work [17,18,19,20]. There has also been recent interest in developing classical algorithms to simulate Gaussian Boson Sampling [22,23,24,25,26], the variant used by Lu, Pan et al. to demonstrate a quantum advantage [12]. It remains open to see if similar methods can also be used to distinguish Gaussian Boson Sampling experiments from their classical simulations.

► BibTeX data

► References

Cited by

This View is published in Quantum Views under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.