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 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•105 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•128 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•23 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•203 citations

Statistical Analysis for Collision-free Boson Sampling

He-Liang Huang, Han-Sen Zhong, Tan Li +5 more

Boson sampling is strongly believed to be intractable for classical computers but solvable with photons in linear optics, which raises widespread concern as a rapid way to demonstrate the quantum supremacy. However, due to its solution is mathematically unverifiable, how to certify the experimental results becomes a major difficulty in the boson sampling experiment. Here, we develop a statistical analysis scheme to experimentally certify the collision-free boson sampling. Numerical simulations are performed to show the feasibility and practicability of our scheme, and the effects of realistic experimental conditions are also considered, demonstrating that our proposed scheme is experimentally friendly. Moreover, our broad approach is expected to be generally applied to investigate multi-particle coherent dynamics beyond the boson sampling.

Scientific Reports•Nov 6, 2017•5 citations

Benchmarking a boson sampler with Hamming nets

Ilia A. Iakovlev, O. M. Sotnikov, I. V. Dyakonov +4 more

Analyzing the properties of complex quantum systems is crucial for further development of quantum devices, yet this task is typically challenging and demanding with respect to the required amount of measurements. Special attention to this problem appears within the context of characterizing outcomes of noisy intermediate-scale quantum devices, which produce quantum states with specific properties so that it is expected to be hard to simulate such states using classical resources. In this work, we address the problem of characterization of a boson sampling device, which uses the interference of input photons to produce samples of nontrivial probability distributions that at certain condition are hard to obtain classically. For realistic experimental conditions the problem is to probe multiphoton interference with a limited number of the measurement outcomes without collisions and repetitions. By constructing networks on the measurement outcomes, we demonstrate the possibility to discriminate between regimes of indistinguishable and distinguishable bosons by quantifying the structures of the corresponding networks. Based on this, we propose a machine-learning-based protocol to benchmark a boson sampler with unknown scattering matrix. Notably, the protocol works in the most challenging regimes of having a very limited number of bitstrings without collisions and repetitions. As we expect, our framework can be directly applied for characterizing boson sampling devices that are currently available in experiments.

arXiv:2305.10946•Physical Review A•Dec 19, 2023•7 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 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.
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.
Boson sampling is strongly believed to be intractable for classical computers but solvable with photons in linear optics, which raises widespread concern as a rapid way to demonstrate the quantum supremacy. However, due to its solution is mathematically unverifiable, how to certify the experimental results becomes a major difficulty in the boson sampling experiment. Here, we develop a statistical analysis scheme to experimentally certify the collision-free boson sampling. Numerical simulations are performed to show the feasibility and practicability of our scheme, and the effects of realistic experimental conditions are also considered, demonstrating that our proposed scheme is experimentally friendly. Moreover, our broad approach is expected to be generally applied to investigate multi-particle coherent dynamics beyond the boson sampling.
Analyzing the properties of complex quantum systems is crucial for further development of quantum devices, yet this task is typically challenging and demanding with respect to the required amount of measurements. Special attention to this problem appears within the context of characterizing outcomes of noisy intermediate-scale quantum devices, which produce quantum states with specific properties so that it is expected to be hard to simulate such states using classical resources. In this work, we address the problem of characterization of a boson sampling device, which uses the interference of input photons to produce samples of nontrivial probability distributions that at certain condition are hard to obtain classically. For realistic experimental conditions the problem is to probe multiphoton interference with a limited number of the measurement outcomes without collisions and repetitions. By constructing networks on the measurement outcomes, we demonstrate the possibility to discriminate between regimes of indistinguishable and distinguishable bosons by quantifying the structures of the corresponding networks. Based on this, we propose a machine-learning-based protocol to benchmark a boson sampler with unknown scattering matrix. Notably, the protocol works in the most challenging regimes of having a very limited number of bitstrings without collisions and repetitions. As we expect, our framework can be directly applied for characterizing boson sampling devices that are currently available in experiments.