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

arXiv:1812.08978 · Physical Review A

Boson sampling with Gaussian input states: Toward efficient scaling and certification

Raphael A. Abrahão, Arman Mansouri, Austin P. Lund

Published Nov 26, 2024• 1 citation
arXivHTMLPDF

Abstract

A universal quantum computer of large scale is not available yet, however, intermediate models of quantum computation would still permit demonstrations of a quantum computational advantage over classical computing and could challenge the extended Church-Turing thesis. One of these models based on single photons interacting via linear optics is called boson sampling. Although boson sampling was demonstrated and the threshold to claim quantum computational advantage was achieved, the question of how to scale up boson sampling experiments remains. To make progress with this problem, here we present a practically achievable pathway to scale boson sampling experiments by combining continuous-variable quantum information and temporal encoding. We propose the combination of switchable dual-homodyne and single-photon detections, the temporal loop technique, and scattershot-based boson sampling. We detail the required assumptions for concluding computational hardness for this configuration. Furthermore, this particular combination of techniques moves towards an efficient scaling and certification of boson sampling, all in a single experimental setup.

DOI
10.1103/physreva.110.052437

Related papers

Boson Sampling with Gaussian input states: efficient scaling and certification.

Raphael A. Abrahão, Austin P. Lund

A universal quantum computer of moderate scale is not available yet, however intermediate models of quantum computation would still permit demonstrations of a quantum computational advantage over classical computing and could challenge the Extended Church-Turing Thesis. One of these models based on single photons interacting via linear optics is called Boson Sampling. Although Boson Sampling was demonstrated and the threshold to claim quantum computational advantage was achieved, the question on how to scale up Boson Sampling experiments remains. To make progress with this problem, here we present a practically achievable pathway to scale Boson Sampling experiments with current technologies by combining continuous-variables quantum information and temporal encoding. We propose the use of switchable dual-homodyne and single-photon detections, the temporal loop technique and scattershot based Boson Sampling. This proposal gives details as to what the required assumptions are and a pathway for scaling Boson Sampling experiments. Furthermore, this particular combination of techniques permits a single efficient implementation of Boson Sampling and efficient certification in a single experimental setup.

•Nov 29, 2021•0 citations

Boson Sampling with efficient scaling and efficient verification

Raphael A. Abrahão, Austin P. Lund

A universal quantum computer of moderate scale is not available yet, however intermediate models of quantum computation would still permit demonstrations of a quantum computational advantage over classical computing and could challenge the Extended Church-Turing Thesis. One of these models based on single photons interacting via linear optics is called Boson Sampling. Proof-of-principle Boson Sampling has been demonstrated, but the number of photons used for these demonstrations is below the level required to claim quantum computational advantage. To make progress with this problem, here we conclude that the most practically achievable pathway to scale Boson Sampling experiments with current technologies is by combining continuous-variables quantum information and temporal encoding. We propose the use of switchable dual-homodyne and single-photon detections, the temporal loop technique and scattershot based Boson Sampling. This proposal gives details as to what the required assumptions are and a pathway for a quantum optical demonstration of quantum computational advantage. Furthermore, this particular combination of techniques permits a single efficient implementation of Boson Sampling and efficient verification in a single experimental setup.

•Dec 21, 2018•1 citation

Continuous-Variables Boson Sampling: Scaling and Verification

Raphael A. Abrahão, Austin P. Lund

A universal quantum computer of moderate scale is not available yet, however intermediate models of quantum computation would still permit demonstrations of a quantum computational advantage over classical computing and could challenge the Extended Church-Turing Thesis. One of these models based on single photons interacting via linear optics is called Boson Sampling. Proof-of-principle Boson Sampling has been demonstrated, but the number of photons used for these demonstrations is below the level required to claim quantum computational advantage. To make progress with this problem, here we conclude that the most practically achievable pathway to scale Boson Sampling experiments with current technologies is by combining continuous-variables quantum information and temporal encoding. We propose the use of switchable dual-homodyne and single-photon detections, the temporal loop technique and scattershot based Boson Sampling. This proposal gives details as to what the required assumptions are and a pathway for a quantum optical demonstration of quantum computational advantage. Furthermore, this particular combination of techniques permits a single efficient implementation of Boson Sampling and efficient verification in a single experimental setup.

•Dec 21, 2018•3 citations

Boson sampling with Gaussian measurements

Levon Chakhmakhchyan, Nicolas J. Cerf

We develop an alternative boson sampling model operating on single-photon states followed by linear interferometry and Gaussian measurements. The hardness proof for simulating such continuous-variable measurements is established in two main steps, making use of the symmetry of quantum evolution under time reversal. Namely, we first construct a twofold version of scattershot boson sampling in which, as opposed to the original proposal, both legs of a collection of two-mode squeezed vacuum states undergo parallel linear-optical transformations. This twofold scattershot model yields, as a corollary, an instance of boson sampling from Gaussian states where photon counting is hard to simulate. Then, a time-reversed setup is used to exhibit a boson sampling model in which the simulation of Gaussian measurements---namely the outcome of eight-port homodyne detection---is proven to be computationally hard. These results illustrate how the symmetry of quantum evolution under time reversal may serve as a tool for analyzing the computational complexity of novel physically motivated computational problems.

arXiv:1705.05299•Physical Review A•Sep 14, 2017•53 citations

Gaussian Boson Sampling Complexity

Andrew Tanggara

It remains questionable whether all physically realizable computational model can be simulated by currently available digital computer in an efficient manner. The theory of Quantum Mechanics offers an answer to this question through one of its branches that intersects with Computer Science, known as Quantum Computing. It claims that current computers, which is operating based on classical mechanics cannot efficiently simulate quantum mechanical process. Under this claim, a computer that is operating based on quantum mechanics holds more computational power than classical computers, promising a possibility to computationally solve problems that are classically intractable. To show that this claim holds, numerous quantum computational models have been proposed and analyzed through the lens of Computational Complexity Theory, providing a rigorous notion of efficiency. Models that are more feasible experimentally, although not necessarily universal, have also been of a particular interests given the numerous complicated challenges surrounding the experimental implementation of a universal quantum computer. One of this non-universal models is called Gaussian Boson Sampling (GBS), which embraces the methods of Quantum Optics by sampling the number of photon outputs from a linear optical network as a means to process quantum information. Compared to its prototype model, Boson Sampling, GBS is more experimentally feasible due to its method of generating photon that is based on the Continuous Variable (CV) paradigm of Quantum Information. Nevertheless as with Boson Sampling, it was also shown that classical simulation of GBS cannot be performed efficiently under some highly plausible conjectures. In the work presented in this thesis, we probe the complexity of classically constructing the probability distribution induced by GBS using the method of Quantum Homodyne Tomography. Instead of photon number measurement, this method further embraces the CV paradigm in the measurement of GBS by using Homodyne measurements that outputs real numbers. Sample data obtained from the measurement outcomes is then classically processed using Pattern Functions, which we use to approximate the probability distribution of GBS. A series of computer simulations that approximates some probability values of GBS are presented here, which shows that the number of samples needed to decrease the error of the approximation increases rapidly for more accurate approximation. We have derived a bound for the approximation error which can be achieved given that the sampled data satisfies a certain statistical property. This statistical property can eventually be satisfied as the number of Homodyne samples increases. Having shown another evidence for the complexity of approximating GBS using Homodyne Tomography, we further investigate the nature of the complexity of GBS by analyzing its classical-quantum computational boundary in the spectrum of amount of noise present in a GBS setup. In doing this, we built our discussions on the measure of non-classicality using the presence of negative values in the Quasi-probability distribution (QPD) representation of states of a quantum system. We then discuss existing results that shows the possibility of efficient classical simulation of a quantum computational model given a sufficient amount of noise. These results impose a necessary criteria of the minimum amount of noise that an experiment has to surpass in order for it to be impossible to simulate classically in an efficient manner. We extend this idea for GBS, where we propose a modified GBS where we consider noise in its measurements that opens a way for a possible formulation of a noise condition that a GBS experiment has to fulfill to rule out possible efficient classical simulation. To further probe the classical-quantum computational boundary, we also propose a different quantum computational model called the Photon-added Thermal State CV-Sampling (PATS CVS), which can be formulated similarly to our noisy GBS model. We then discuss existing results that analyzes the negativity of the QPD representation of a noisy Photon-added Thermal state (PATS), which constitutes the inputs for PATS CVS. Using the result that shows the quantum-classical transition in terms of the QPD negativity for a PATS state when the amount of noise changes, we discuss the potential of PATS CVS model as a possible avenue to further probe the transition between efficiently simulable and non-efficiently simulable quantum mechanical experiment.

•Jan 1, 2021•0 citations

Reaching Quantum Supremacy with a Boson Sampling Experiment

Ludovico Latmiral

Boson Sampling represents a promising witness of the supremacy of quantum systems as a resource for the solution of computational problems. The classical hardness of Boson Sampling has been related to the so called Permanent-of-Gaussians Conjecture and has been extended to some generalizations such as scattershot Boson Sampling, approximate and lossy sampling under some reasonable constraints. However, it is still unclear how demanding these bounds are for a quantum experimental sampler. Starting from a state of the art analysis and focusing on the foreseeable practical conditions needed to reach quantum supremacy, we look at different techniques and present a more general and effective solution. We apply our approach to both the experimental suggestions presented to date and we eventually find in both cases a new threshold that is less error sensitive and experimentally more feasible.

arXiv:1511.08161•Nov 25, 2015•0 citations
A universal quantum computer of large scale is not available yet, however, intermediate models of quantum computation would still permit demonstrations of a quantum computational advantage over classical computing and could challenge the extended Church-Turing thesis. One of these models based on single photons interacting via linear optics is called boson sampling. Although boson sampling was demonstrated and the threshold to claim quantum computational advantage was achieved, the question of how to scale up boson sampling experiments remains. To make progress with this problem, here we present a practically achievable pathway to scale boson sampling experiments by combining continuous-variable quantum information and temporal encoding. We propose the combination of switchable dual-homodyne and single-photon detections, the temporal loop technique, and scattershot-based boson sampling. We detail the required assumptions for concluding computational hardness for this configuration. Furthermore, this particular combination of techniques moves towards an efficient scaling and certification of boson sampling, all in a single experimental setup.
A universal quantum computer of moderate scale is not available yet, however intermediate models of quantum computation would still permit demonstrations of a quantum computational advantage over classical computing and could challenge the Extended Church-Turing Thesis. One of these models based on single photons interacting via linear optics is called Boson Sampling. Although Boson Sampling was demonstrated and the threshold to claim quantum computational advantage was achieved, the question on how to scale up Boson Sampling experiments remains. To make progress with this problem, here we present a practically achievable pathway to scale Boson Sampling experiments with current technologies by combining continuous-variables quantum information and temporal encoding. We propose the use of switchable dual-homodyne and single-photon detections, the temporal loop technique and scattershot based Boson Sampling. This proposal gives details as to what the required assumptions are and a pathway for scaling Boson Sampling experiments. Furthermore, this particular combination of techniques permits a single efficient implementation of Boson Sampling and efficient certification in a single experimental setup.
A universal quantum computer of moderate scale is not available yet, however intermediate models of quantum computation would still permit demonstrations of a quantum computational advantage over classical computing and could challenge the Extended Church-Turing Thesis. One of these models based on single photons interacting via linear optics is called Boson Sampling. Proof-of-principle Boson Sampling has been demonstrated, but the number of photons used for these demonstrations is below the level required to claim quantum computational advantage. To make progress with this problem, here we conclude that the most practically achievable pathway to scale Boson Sampling experiments with current technologies is by combining continuous-variables quantum information and temporal encoding. We propose the use of switchable dual-homodyne and single-photon detections, the temporal loop technique and scattershot based Boson Sampling. This proposal gives details as to what the required assumptions are and a pathway for a quantum optical demonstration of quantum computational advantage. Furthermore, this particular combination of techniques permits a single efficient implementation of Boson Sampling and efficient verification in a single experimental setup.
A universal quantum computer of moderate scale is not available yet, however intermediate models of quantum computation would still permit demonstrations of a quantum computational advantage over classical computing and could challenge the Extended Church-Turing Thesis. One of these models based on single photons interacting via linear optics is called Boson Sampling. Proof-of-principle Boson Sampling has been demonstrated, but the number of photons used for these demonstrations is below the level required to claim quantum computational advantage. To make progress with this problem, here we conclude that the most practically achievable pathway to scale Boson Sampling experiments with current technologies is by combining continuous-variables quantum information and temporal encoding. We propose the use of switchable dual-homodyne and single-photon detections, the temporal loop technique and scattershot based Boson Sampling. This proposal gives details as to what the required assumptions are and a pathway for a quantum optical demonstration of quantum computational advantage. Furthermore, this particular combination of techniques permits a single efficient implementation of Boson Sampling and efficient verification in a single experimental setup.
We develop an alternative boson sampling model operating on single-photon states followed by linear interferometry and Gaussian measurements. The hardness proof for simulating such continuous-variable measurements is established in two main steps, making use of the symmetry of quantum evolution under time reversal. Namely, we first construct a twofold version of scattershot boson sampling in which, as opposed to the original proposal, both legs of a collection of two-mode squeezed vacuum states undergo parallel linear-optical transformations. This twofold scattershot model yields, as a corollary, an instance of boson sampling from Gaussian states where photon counting is hard to simulate. Then, a time-reversed setup is used to exhibit a boson sampling model in which the simulation of Gaussian measurements---namely the outcome of eight-port homodyne detection---is proven to be computationally hard. These results illustrate how the symmetry of quantum evolution under time reversal may serve as a tool for analyzing the computational complexity of novel physically motivated computational problems.
It remains questionable whether all physically realizable computational model can be simulated by currently available digital computer in an efficient manner. The theory of Quantum Mechanics offers an answer to this question through one of its branches that intersects with Computer Science, known as Quantum Computing. It claims that current computers, which is operating based on classical mechanics cannot efficiently simulate quantum mechanical process. Under this claim, a computer that is operating based on quantum mechanics holds more computational power than classical computers, promising a possibility to computationally solve problems that are classically intractable. To show that this claim holds, numerous quantum computational models have been proposed and analyzed through the lens of Computational Complexity Theory, providing a rigorous notion of efficiency. Models that are more feasible experimentally, although not necessarily universal, have also been of a particular interests given the numerous complicated challenges surrounding the experimental implementation of a universal quantum computer. One of this non-universal models is called Gaussian Boson Sampling (GBS), which embraces the methods of Quantum Optics by sampling the number of photon outputs from a linear optical network as a means to process quantum information. Compared to its prototype model, Boson Sampling, GBS is more experimentally feasible due to its method of generating photon that is based on the Continuous Variable (CV) paradigm of Quantum Information. Nevertheless as with Boson Sampling, it was also shown that classical simulation of GBS cannot be performed efficiently under some highly plausible conjectures. In the work presented in this thesis, we probe the complexity of classically constructing the probability distribution induced by GBS using the method of Quantum Homodyne Tomography. Instead of photon number measurement, this method further embraces the CV paradigm in the measurement of GBS by using Homodyne measurements that outputs real numbers. Sample data obtained from the measurement outcomes is then classically processed using Pattern Functions, which we use to approximate the probability distribution of GBS. A series of computer simulations that approximates some probability values of GBS are presented here, which shows that the number of samples needed to decrease the error of the approximation increases rapidly for more accurate approximation. We have derived a bound for the approximation error which can be achieved given that the sampled data satisfies a certain statistical property. This statistical property can eventually be satisfied as the number of Homodyne samples increases. Having shown another evidence for the complexity of approximating GBS using Homodyne Tomography, we further investigate the nature of the complexity of GBS by analyzing its classical-quantum computational boundary in the spectrum of amount of noise present in a GBS setup. In doing this, we built our discussions on the measure of non-classicality using the presence of negative values in the Quasi-probability distribution (QPD) representation of states of a quantum system. We then discuss existing results that shows the possibility of efficient classical simulation of a quantum computational model given a sufficient amount of noise. These results impose a necessary criteria of the minimum amount of noise that an experiment has to surpass in order for it to be impossible to simulate classically in an efficient manner. We extend this idea for GBS, where we propose a modified GBS where we consider noise in its measurements that opens a way for a possible formulation of a noise condition that a GBS experiment has to fulfill to rule out possible efficient classical simulation. To further probe the classical-quantum computational boundary, we also propose a different quantum computational model called the Photon-added Thermal State CV-Sampling (PATS CVS), which can be formulated similarly to our noisy GBS model. We then discuss existing results that analyzes the negativity of the QPD representation of a noisy Photon-added Thermal state (PATS), which constitutes the inputs for PATS CVS. Using the result that shows the quantum-classical transition in terms of the QPD negativity for a PATS state when the amount of noise changes, we discuss the potential of PATS CVS model as a possible avenue to further probe the transition between efficiently simulable and non-efficiently simulable quantum mechanical experiment.
Boson Sampling represents a promising witness of the supremacy of quantum systems as a resource for the solution of computational problems. The classical hardness of Boson Sampling has been related to the so called Permanent-of-Gaussians Conjecture and has been extended to some generalizations such as scattershot Boson Sampling, approximate and lossy sampling under some reasonable constraints. However, it is still unclear how demanding these bounds are for a quantum experimental sampler. Starting from a state of the art analysis and focusing on the foreseeable practical conditions needed to reach quantum supremacy, we look at different techniques and present a more general and effective solution. We apply our approach to both the experimental suggestions presented to date and we eventually find in both cases a new threshold that is less error sensitive and experimentally more feasible.