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

New Journal of Physics

Is my boson sampler working?

Marco Bentivegna, Nicolò Spagnolo, Fabio Sciarrino

Published Apr 1, 2016• 13 citations
Publisher

Abstract

Abstract Is it possible to assess the correct functioning of a quantum device which eludes efficient computation of the expected results? The BosonSampling protocol is one of the best candidates to experimentally demonstrate the superior computational power of quantum mechanics, but the problem of its results certification requires the development of new methodologies, when the size of the problem becomes too large for a complete classical simulation. A recent work (Walschaers et al 2016 New J. Phys. 18 032001) has provided a significant step forward in this direction, by developing a statistical test to identify particle types in a many-body interference pattern. This tool can be applied in a general scenario to assess and investigate multi-particle coherent dynamics.

DOI
10.1088/1367-2630/18/4/041001

Related papers

Statistical benchmark for BosonSampling

Mattia Walschaers, Jack Kuipers, Juan Diego Urbina +4 more

Boson samplers-set-ups that generate complex many-particle output states through the transmission of elementary many-particle input states across a multitude of mutually coupled modes-promise the efficient quantum simulation of a classically intractable computational task, and challenge the extended Church-Turing thesis, one of the fundamental dogmas of computer science. However, as in all experimental quantum simulations of truly complex systems, one crucial problem remains: how to certify that a given experimental measurement record unambiguously results from enforcing the claimed dynamics, on bosons, fermions or distinguishable particles? Here we offer a statistical solution to the certification problem, identifying an unambiguous statistical signature of many-body quantum interference upon transmission across a multimode, random scattering device. We show that statistical analysis of only partial information on the output state allows to characterise the imparted dynamics through particle type-specific features of the emerging interference patterns. The relevant statistical quantifiers are classically computable, define a falsifiable benchmark for BosonSampling, and reveal distinctive features of many-particle quantum dynamics, which go much beyond mere bunching or anti-bunching effects.

•Mar 1, 2016•70 citations

Statistical benchmark for BosonSampling

Mattia Walschaers, Jack Kuipers, Juan-Diego Urbina +4 more

Boson samplers-set-ups that generate complex many-particle output states through the transmission of elementary many-particle input states across a multitude of mutually coupled modespromise the efficient quantum simulation of a classically intractable computational task, and challenge the extended Church-Turing thesis, one of the fundamental dogmas of computer science.However, as in all experimental quantum simulations of truly complex systems, one crucial problem remains: how to certify that a given experimental measurement record unambiguously results from enforcing the claimed dynamics, on bosons, fermions or distinguishable particles?Here we offer a statistical solution to the certification problem, identifying an unambiguous statistical signature of many-body quantum interference upon transmission across a multimode, random scattering device.We show that statistical analysis of only partial information on the output state allows to characterise the imparted dynamics through particle type-specific features of the emerging interference patterns.The relevant statistical quantifiers are classically computable, define a falsifiable benchmark for BosonSampling, and reveal distinctive features of many-particle quantum dynamics, which go much beyond mere bunching or anti-bunching effects.

arXiv:1410.8547•New Journal of Physics•Mar 3, 2016•87 citations

Stringent and Efficient Assessment of Boson-Sampling Devices

Malte C. Tichy, Klaus Mayer, Andreas Buchleitner +1 more

Boson sampling holds the potential to experimentally falsify the extended Church-Turing thesis. The computational hardness of boson sampling, however, complicates the certification that an experimental device yields correct results in the regime in which it outmatches classical computers. To certify a boson sampler, one needs to verify quantum predictions and rule out models that yield these predictions without true many-boson interference. We show that a semiclassical model for many-boson propagation reproduces coarse-grained observables that are proposed as witnesses of boson sampling. A test based on Fourier matrices is demonstrated to falsify physically plausible alternatives to coherent many-boson propagation.

arXiv:1312.3080•Physical Review Letters•Jul 9, 2014•127 citations

Quantum Science and Technology / Validating multi-photon quantum interference with finite data

Fulvio Flamini, Mattia Walschaers, Nicolò Spagnolo +3 more

Multi-particle interference is a key resource for quantum information processing, as exemplified by Boson Sampling. Hence, given its fragile nature, an essential desideratum is a solid and reliable framework for its validation. However, while several protocols have been introduced to this end, the approach is still fragmented and fails to build a big picture for future developments. In this work, we propose an operational approach to validation that encompasses and strengthens the state of the art for these protocols. To this end, we consider the Bayesian hypothesis testing and the statistical benchmark as most favorable protocols for small- and large-scale applications, respectively. We numerically investigate their operation with finite sample size, extending previous tests to larger dimensions, and against two adversarial algorithms for classical simulation: the mean-field sampler and the metropolized independent sampler. To evidence the actual need for refined validation techniques, we show how the assessment of numerically simulated data depends on the available sample size, as well as on the internal hyper-parameters and other practically relevant constraints. Our analyses provide general insights into the challenge of validation, and can inspire the design of algorithms with a measurable quantum advantage.

•Jan 1, 2020•9 citations

Certification of Boson Sampling Devices with Coarse-Grained Measurements

Sheng-Tao Wang, Luming Duan

A boson sampling device could efficiently sample from the output probability distribution of noninteracting bosons undergoing many-body interference. This problem is not only classically intractable, but its solution is also believed to be classically unverifiable. Hence, a major difficulty in experiment is to ensure a boson sampling device performs correctly. We present an experimental friendly scheme to extract useful and robust information from the quantum boson samplers based on coarse-grained measurements. The procedure can be applied to certify the equivalence of boson sampling devices while ruling out alternative fraudulent devices. We perform numerical simulations to demonstrate the feasibility of the method and consider the effects of realistic noise. Our approach is expected to be generally applicable to other many-body certification tasks beyond the boson sampling problem.

arXiv:1601.02627•Jan 11, 2016•15 citations

Quantum sampling problems, BosonSampling and quantum supremacy

Austin P. Lund, Michael J. Bremner, Timothy C. Ralph

Abstract There is a large body of evidence for the potential of greater computational power using information carriers that are quantum mechanical over those governed by the laws of classical mechanics. But the question of the exact nature of the power contributed by quantum mechanics remains only partially answered. Furthermore, there exists doubt over the practicality of achieving a large enough quantum computation that definitively demonstrates quantum supremacy. Recently the study of computational problems that produce samples from probability distributions has added to both our understanding of the power of quantum algorithms and lowered the requirements for demonstration of fast quantum algorithms. The proposed quantum sampling problems do not require a quantum computer capable of universal operations and also permit physically realistic errors in their operation. This is an encouraging step towards an experimental demonstration of quantum algorithmic supremacy. In this paper, we will review sampling problems and the arguments that have been used to deduce when sampling problems are hard for classical computers to simulate. Two classes of quantum sampling problems that demonstrate the supremacy of quantum algorithms are BosonSampling and Instantaneous Quantum Polynomial-time Sampling. We will present the details of these classes and recent experimental progress towards demonstrating quantum supremacy in BosonSampling.

arXiv:1702.03061•npj Quantum Information•Apr 5, 2017•184 citations
Abstract Is it possible to assess the correct functioning of a quantum device which eludes efficient computation of the expected results? The BosonSampling protocol is one of the best candidates to experimentally demonstrate the superior computational power of quantum mechanics, but the problem of its results certification requires the development of new methodologies, when the size of the problem becomes too large for a complete classical simulation. A recent work (Walschaers et al 2016 New J. Phys. 18 032001) has provided a significant step forward in this direction, by developing a statistical test to identify particle types in a many-body interference pattern. This tool can be applied in a general scenario to assess and investigate multi-particle coherent dynamics.
Boson samplers-set-ups that generate complex many-particle output states through the transmission of elementary many-particle input states across a multitude of mutually coupled modes-promise the efficient quantum simulation of a classically intractable computational task, and challenge the extended Church-Turing thesis, one of the fundamental dogmas of computer science. However, as in all experimental quantum simulations of truly complex systems, one crucial problem remains: how to certify that a given experimental measurement record unambiguously results from enforcing the claimed dynamics, on bosons, fermions or distinguishable particles? Here we offer a statistical solution to the certification problem, identifying an unambiguous statistical signature of many-body quantum interference upon transmission across a multimode, random scattering device. We show that statistical analysis of only partial information on the output state allows to characterise the imparted dynamics through particle type-specific features of the emerging interference patterns. The relevant statistical quantifiers are classically computable, define a falsifiable benchmark for BosonSampling, and reveal distinctive features of many-particle quantum dynamics, which go much beyond mere bunching or anti-bunching effects.
Boson samplers-set-ups that generate complex many-particle output states through the transmission of elementary many-particle input states across a multitude of mutually coupled modespromise the efficient quantum simulation of a classically intractable computational task, and challenge the extended Church-Turing thesis, one of the fundamental dogmas of computer science.However, as in all experimental quantum simulations of truly complex systems, one crucial problem remains: how to certify that a given experimental measurement record unambiguously results from enforcing the claimed dynamics, on bosons, fermions or distinguishable particles?Here we offer a statistical solution to the certification problem, identifying an unambiguous statistical signature of many-body quantum interference upon transmission across a multimode, random scattering device.We show that statistical analysis of only partial information on the output state allows to characterise the imparted dynamics through particle type-specific features of the emerging interference patterns.The relevant statistical quantifiers are classically computable, define a falsifiable benchmark for BosonSampling, and reveal distinctive features of many-particle quantum dynamics, which go much beyond mere bunching or anti-bunching effects.
Boson sampling holds the potential to experimentally falsify the extended Church-Turing thesis. The computational hardness of boson sampling, however, complicates the certification that an experimental device yields correct results in the regime in which it outmatches classical computers. To certify a boson sampler, one needs to verify quantum predictions and rule out models that yield these predictions without true many-boson interference. We show that a semiclassical model for many-boson propagation reproduces coarse-grained observables that are proposed as witnesses of boson sampling. A test based on Fourier matrices is demonstrated to falsify physically plausible alternatives to coherent many-boson propagation.
Multi-particle interference is a key resource for quantum information processing, as exemplified by Boson Sampling. Hence, given its fragile nature, an essential desideratum is a solid and reliable framework for its validation. However, while several protocols have been introduced to this end, the approach is still fragmented and fails to build a big picture for future developments. In this work, we propose an operational approach to validation that encompasses and strengthens the state of the art for these protocols. To this end, we consider the Bayesian hypothesis testing and the statistical benchmark as most favorable protocols for small- and large-scale applications, respectively. We numerically investigate their operation with finite sample size, extending previous tests to larger dimensions, and against two adversarial algorithms for classical simulation: the mean-field sampler and the metropolized independent sampler. To evidence the actual need for refined validation techniques, we show how the assessment of numerically simulated data depends on the available sample size, as well as on the internal hyper-parameters and other practically relevant constraints. Our analyses provide general insights into the challenge of validation, and can inspire the design of algorithms with a measurable quantum advantage.
A boson sampling device could efficiently sample from the output probability distribution of noninteracting bosons undergoing many-body interference. This problem is not only classically intractable, but its solution is also believed to be classically unverifiable. Hence, a major difficulty in experiment is to ensure a boson sampling device performs correctly. We present an experimental friendly scheme to extract useful and robust information from the quantum boson samplers based on coarse-grained measurements. The procedure can be applied to certify the equivalence of boson sampling devices while ruling out alternative fraudulent devices. We perform numerical simulations to demonstrate the feasibility of the method and consider the effects of realistic noise. Our approach is expected to be generally applicable to other many-body certification tasks beyond the boson sampling problem.
Abstract There is a large body of evidence for the potential of greater computational power using information carriers that are quantum mechanical over those governed by the laws of classical mechanics. But the question of the exact nature of the power contributed by quantum mechanics remains only partially answered. Furthermore, there exists doubt over the practicality of achieving a large enough quantum computation that definitively demonstrates quantum supremacy. Recently the study of computational problems that produce samples from probability distributions has added to both our understanding of the power of quantum algorithms and lowered the requirements for demonstration of fast quantum algorithms. The proposed quantum sampling problems do not require a quantum computer capable of universal operations and also permit physically realistic errors in their operation. This is an encouraging step towards an experimental demonstration of quantum algorithmic supremacy. In this paper, we will review sampling problems and the arguments that have been used to deduce when sampling problems are hard for classical computers to simulate. Two classes of quantum sampling problems that demonstrate the supremacy of quantum algorithms are BosonSampling and Instantaneous Quantum Polynomial-time Sampling. We will present the details of these classes and recent experimental progress towards demonstrating quantum supremacy in BosonSampling.