Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Conference on Lasers and Electro-Optics

Experimental BosonSampling in a Tunable Optical Network

Matthew A. Broome, Alessandro Fedrizzi, Saleh Rahimi-Keshari, Justin Dove, Scott Aaronson, Timothy C. Ralph, Andrew G. White

Published Jan 1, 2013• 0 citations
Publisher

Abstract

We report an experimental demonstration of BosonSampling: an intermediate-model of quantum-computing. We verify that the scattering probabilities for three-photon interference are given by permanents of sub-matrices of a larger unitary matrix describing the optical network.
DOI
10.1364/cleo_qels.2013.qw1c.3

Related papers

BosonSampling with lost photons

Scott Aaronson, Daniel J. Brod

BosonSampling is an intermediate model of quantum computation where linear-optical networks are used to solve sampling problems expected to be hard for classical computers. Since these devices are not expected to be universal for quantum computation, it remains an open question of whether any error-correction techniques can be applied to them, and thus it is important to investigate how robust the model is under natural experimental imperfections, such as losses and imperfect control of parameters. Here, we investigate the complexity of BosonSampling under photon losses, more specifically, the case where an unknown subset of the photons is randomly lost at the sources. We show that if $k$ out of $n$ photons are lost, then we cannot sample classically from a distribution that is $1/{n}^{\mathrm{\ensuremath{\Theta}}(k)}$ close (in total variation distance) to the ideal distribution, unless a ${\text{BPP}}^{\text{NP}}$ machine can estimate the permanents of Gaussian matrices in ${n}^{O(k)}$ time. In particular, if $k$ is constant, this implies that simulating lossy BosonSampling is hard for a classical computer, under exactly the same complexity assumption used for the original lossless case.

arXiv:1510.05245•Physical Review A•Jan 21, 2016•88 citations

The role of complexity theory in quantum optics—a tutorial for BosonSampling

Jonathan P. Olson

Abstract BosonSampling is a recent development in linear optics which has stimulated a number of new computational models and algorithms in quantum computing. Much of this interest follows from the computational complexity arguments which show that the particular quantum system in which BosonSampling resides is difficult to simulate with a classical computer (assuming highly plausible conjectures) Arkhipov and Aaronson (2011 Proc. ACM STOC (New York) , p 333). These arguments, however, require some understanding of both quantum optics and complexity theory—topics that are rarely seen together. This tutorial is intended to introduce a reader to the topic who has at least a basic knowledge of quantum mechanics or quantum information theory, but may be unfamiliar with either quantum optics or complexity theory. Included is some historic context as well as an outlook on the potential for BosonSampling to be the first experimental demonstration of quantum supremacy. The emphasis of the first section is to develop a general context for the subfields of quantum optics and computer science that intersect to form the BosonSampling problem. This begins with a historical introduction and a background of quantum optics. We then progress to the physical system—quantum optical networks—where BosonSampling is defined. Finally, we provide a short introduction to computational complexity theory to provide a structure where the essence behind the BosonSampling result can be discerned. The second section focuses on the BosonSampling result itself, seeking to understand the computational complexity aspects of passive linear optical networks, and what consequences this may have. Some effort is spent discussing a number of issues inherent in the BosonSampling problem that are roadblocks to limiting the scope of its applicability, but that have made progress recently and remain active topics of research. The third short section touches on the relationship between BosonSampling and other quantum computing protocols. Namely, other settings and architectures that inherit the same complexity as BosonSampling will be presented, as well as giving a summary of experimental efforts to implement BosonSampling . We discuss similarities between BosonSampling and other quantum algorithms. In the final section, some comments are presented considering future research related to the problems and protocols found in this tutorial. We suggest other unexplored directions of study which may have some bearing on the complexity of quantum optics. Also included is a glossary of complexity terms used throughout the tutorial.

Journal of Optics•Oct 10, 2018•6 citations

BosonSampling is robust against small errors in the network matrix

Alex Arkhipov

We demonstrate the robustness of BosonSampling against imperfections in the linear optical network that cause a small deviation in the matrix it implements. We show that applying a noisy matrix $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{U}$ that is within $\ensuremath{\epsilon}$ of the desired matrix $U$ in operator norm leads to an output distribution that is within $\ensuremath{\epsilon}n$ of the desired distribution in variation distance, where $n$ is the number of photons. This lets us derive a sufficient tolerance for beam splitters and phase shifters in the network. This result only concerns errors that result from the network encoding a different unitary than desired and not from other sources of noise such as photon loss and partial distinguishability.

arXiv:1412.2516•Physical Review A•Dec 14, 2015•49 citations

Quantum computation with identical bosons

A. A. Архипов

We investigate the computational complexity of quantum computing with identical noninteracting bosons, such as that in a linear optical system.We explore the challenges in building devices that implement this model and in certifying their correctness.In work done with Scott Aaronson, we introduce BOSONSAMPLING, a computational model of quantum linear optics [1].We argue that the statistical distribution of outcomes cannot be reproduced by any classical device in a reasonable time span.This gives hands-on evidence of quantum advantage, that there are quantum phenomena are prohibitive to simulate in the classical world.Moreover, this quantum advantage is already present in limited optical systems, suggesting a lower bar to building devices that exhibit super-classical computation.We lay out the computational complexity argument for the classical difficulty of simulating BOSONSAM-PLING.An efficient classical simulation would have unlikely complexity consequences for the polynomial hierarchy PH.We look into the difficulties in proving an analogous approximate result, including the conjectures that seem to be needed to push it through.We then discuss experimental implementations of BOSONSAMPLING.The scalability of current implementations is limited by various sources of noise that accumulate as the problem size grows.We prove a result [51 that pertains to the inexactnesses of components that comprise the linear optical network, giving bounds on the tolerances that suffice to obtain an output distribution close to the ideal one.Finally, we look at the challenge of certifying a BOSONSAMPLING device.We show the impossibility of one technique, to use a submatrix whose permanent is so large that its corresponding outcome appears very frequently.Joint work with Aaronson [21 argues that the outputs of a BOSONSAMPLING device can be verified not to come from a uniform distribution.Results on the statistical bunching of bosons obtained with Kuperberg [61 are another approach to certification.We further present a novel certification technique based on classically estimating the distribution of integer combinations of the boson counts.

•Jan 1, 2017•0 citations

Analysis of circuit imperfections in BosonSampling

Anthony Leverrier, Raúl García−Patrón

BosonSampling is a problem where a quantum computer offers a provable speedup over classical computers. Its main feature is that it can be solved with current linear optics technology, without the need for a full quantum computer. In this work, we investigate whether an experimentally realistic BosonSampler can really solve BosonSampling without any fault-tolerance mechanism. More precisely, we study how the unavoidable errors linked to an imperfect calibration of the optical elements affect the final result of the computation. We show that the fidelity of each optical element must be at least 1 − O(1/n^2 ), where n refers to the number of single photons in the scheme. Such a requirement seems to be achievable with state-of-the-art equipment.

arXiv:1309.4687•Quantum Information and Computation•Apr 1, 2015•42 citations

Experimental BosonSampling

Matthew A. Broome, Alessandro Fedrizzi, Saleh Rahimi-Keshari +4 more

The extended Church-Turing theeie posits that any computable function can be oalculated efficitntly by a probabilistic Turing machine. If this thesis held true, thee global effort; to build quantum computers might ultimhiely be unnecessary. The thesis would however be strongly contradicted by a physical device that efficiently performs a task believed to be intractable for classical computers. BOSONSAMPLING—the sampling from a distribution of n photons undergoing some linear-optical process—is a recently developed, and experimentally accessible example of such a task [1].

The Rochester Conferences on Coherence and Quantum Optics and the Quantum Information and Measurement meeting•Jan 1, 2013•94 citations
BosonSampling is an intermediate model of quantum computation where linear-optical networks are used to solve sampling problems expected to be hard for classical computers. Since these devices are not expected to be universal for quantum computation, it remains an open question of whether any error-correction techniques can be applied to them, and thus it is important to investigate how robust the model is under natural experimental imperfections, such as losses and imperfect control of parameters. Here, we investigate the complexity of BosonSampling under photon losses, more specifically, the case where an unknown subset of the photons is randomly lost at the sources. We show that if kkk out of nnn photons are lost, then we cannot sample classically from a distribution that is $1/{n}^{\mathrm{\ensuremath{\Theta}}(k)}$ close (in total variation distance) to the ideal distribution, unless a BPPNP{\text{BPP}}^{\text{NP}}BPPNP machine can estimate the permanents of Gaussian matrices in nO(k){n}^{O(k)}nO(k) time. In particular, if kkk is constant, this implies that simulating lossy BosonSampling is hard for a classical computer, under exactly the same complexity assumption used for the original lossless case.
Abstract BosonSampling is a recent development in linear optics which has stimulated a number of new computational models and algorithms in quantum computing. Much of this interest follows from the computational complexity arguments which show that the particular quantum system in which BosonSampling resides is difficult to simulate with a classical computer (assuming highly plausible conjectures) Arkhipov and Aaronson (2011 Proc. ACM STOC (New York) , p 333). These arguments, however, require some understanding of both quantum optics and complexity theory—topics that are rarely seen together. This tutorial is intended to introduce a reader to the topic who has at least a basic knowledge of quantum mechanics or quantum information theory, but may be unfamiliar with either quantum optics or complexity theory. Included is some historic context as well as an outlook on the potential for BosonSampling to be the first experimental demonstration of quantum supremacy. The emphasis of the first section is to develop a general context for the subfields of quantum optics and computer science that intersect to form the BosonSampling problem. This begins with a historical introduction and a background of quantum optics. We then progress to the physical system—quantum optical networks—where BosonSampling is defined. Finally, we provide a short introduction to computational complexity theory to provide a structure where the essence behind the BosonSampling result can be discerned. The second section focuses on the BosonSampling result itself, seeking to understand the computational complexity aspects of passive linear optical networks, and what consequences this may have. Some effort is spent discussing a number of issues inherent in the BosonSampling problem that are roadblocks to limiting the scope of its applicability, but that have made progress recently and remain active topics of research. The third short section touches on the relationship between BosonSampling and other quantum computing protocols. Namely, other settings and architectures that inherit the same complexity as BosonSampling will be presented, as well as giving a summary of experimental efforts to implement BosonSampling . We discuss similarities between BosonSampling and other quantum algorithms. In the final section, some comments are presented considering future research related to the problems and protocols found in this tutorial. We suggest other unexplored directions of study which may have some bearing on the complexity of quantum optics. Also included is a glossary of complexity terms used throughout the tutorial.
We demonstrate the robustness of BosonSampling against imperfections in the linear optical network that cause a small deviation in the matrix it implements. We show that applying a noisy matrix $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{U}$ that is within $\ensuremath{\epsilon}$ of the desired matrix UUU in operator norm leads to an output distribution that is within $\ensuremath{\epsilon}n$ of the desired distribution in variation distance, where nnn is the number of photons. This lets us derive a sufficient tolerance for beam splitters and phase shifters in the network. This result only concerns errors that result from the network encoding a different unitary than desired and not from other sources of noise such as photon loss and partial distinguishability.
We investigate the computational complexity of quantum computing with identical noninteracting bosons, such as that in a linear optical system.We explore the challenges in building devices that implement this model and in certifying their correctness.In work done with Scott Aaronson, we introduce BOSONSAMPLING, a computational model of quantum linear optics [1].We argue that the statistical distribution of outcomes cannot be reproduced by any classical device in a reasonable time span.This gives hands-on evidence of quantum advantage, that there are quantum phenomena are prohibitive to simulate in the classical world.Moreover, this quantum advantage is already present in limited optical systems, suggesting a lower bar to building devices that exhibit super-classical computation.We lay out the computational complexity argument for the classical difficulty of simulating BOSONSAM-PLING.An efficient classical simulation would have unlikely complexity consequences for the polynomial hierarchy PH.We look into the difficulties in proving an analogous approximate result, including the conjectures that seem to be needed to push it through.We then discuss experimental implementations of BOSONSAMPLING.The scalability of current implementations is limited by various sources of noise that accumulate as the problem size grows.We prove a result [51 that pertains to the inexactnesses of components that comprise the linear optical network, giving bounds on the tolerances that suffice to obtain an output distribution close to the ideal one.Finally, we look at the challenge of certifying a BOSONSAMPLING device.We show the impossibility of one technique, to use a submatrix whose permanent is so large that its corresponding outcome appears very frequently.Joint work with Aaronson [21 argues that the outputs of a BOSONSAMPLING device can be verified not to come from a uniform distribution.Results on the statistical bunching of bosons obtained with Kuperberg [61 are another approach to certification.We further present a novel certification technique based on classically estimating the distribution of integer combinations of the boson counts.
BosonSampling is a problem where a quantum computer offers a provable speedup over classical computers. Its main feature is that it can be solved with current linear optics technology, without the need for a full quantum computer. In this work, we investigate whether an experimentally realistic BosonSampler can really solve BosonSampling without any fault-tolerance mechanism. More precisely, we study how the unavoidable errors linked to an imperfect calibration of the optical elements affect the final result of the computation. We show that the fidelity of each optical element must be at least 1 − O(1/n^2 ), where n refers to the number of single photons in the scheme. Such a requirement seems to be achievable with state-of-the-art equipment.
The extended Church-Turing theeie posits that any computable function can be oalculated efficitntly by a probabilistic Turing machine. If this thesis held true, thee global effort; to build quantum computers might ultimhiely be unnecessary. The thesis would however be strongly contradicted by a physical device that efficiently performs a task believed to be intractable for classical computers. BOSONSAMPLING—the sampling from a distribution of n photons undergoing some linear-optical process—is a recently developed, and experimentally accessible example of such a task [1].