Quantum algorithms provide advantages for specific computational and sampling tasks, though little attention has so far been dedicated to the validation of the output of experimental implementations of such algorithms. In this work we address this issue for the Boson Sampling problem, and propose an operational definition of validation. To evidence the actual need for refined validation techniques, we examine two recent protocols: Metropolized independent sampling, to classically simulate Boson Sampling, and a statistical benchmark to validate quantum interference. We show how the acceptance or rejection of numerically simulated data depends on the available sample size, as well as on the internal hyper-parameters and other practically relevant constraints. Our analysis provides general insights into the challenge of validation, and may inspire further research into the design of algorithms with a measurable quantum advantage.
Quantum algorithms provide advantages for specific computational and sampling tasks, though little attention has so far been dedicated to the validation of the output of experimental implementations of such algorithms. In this work we address this issue for the Boson Sampling problem, and propose an operational definition of validation. To evidence the actual need for refined validation techniques, we examine two recent protocols: Metropolized independent sampling, to classically simulate Boson Sampling, and a statistical benchmark to validate quantum interference. We show how the acceptance or rejection of numerically simulated data depends on the available sample size, as well as on the internal hyper-parameters and other practically relevant constraints. Our analysis provides general insights into the challenge of validation, and may inspire further research into the design of algorithms with a measurable quantum advantage.
Abstract 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.
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.
The progressive development of quantum technologies in many areas, ranging from investigation on foundamentals of quantum of mechanics to quantum information and computation, has increased the interest on those problems that can exhibit a quantum advantage. The Boson Sampling problem is a clear example where traditional computers fail in the task of sampling from the distribution of n indistinguishable photons after a propagation in a m-mode optical interferometer. In this context, in the absence of classical algorithms able to simulate efficiently multi-photon interference, the validation of Boson Sampling is still an open problem. Here we investigate a novel approach to Boson Sampling validation based on statistical properties of correlation functions. In particular we discuss its feasibility in actual proof-of-principle experiments. Furthermore we provide an extensive study of the physical resources required to validate experiments, investigating also the role of bosonic bunching in high-dimensional applications. Our investigation confirms the goodness of the validation protocol, paving the way to use this toolbox for the validation of Boson Sampling devices.
Quantum computers solve intractable problems which classically require an exponentially long time to compute. With the development of large-scale experiments that claim quantum advantage, a vital issue has now emerged. What are the errors, and how do they affect the complexity of the problem solved? Large-scale Gaussian boson sampling (GBS) experiments give an example in which random numbers are generated. Despite classical hardness, these have computable benchmarks for checking data validity. While there are other quantum computing architectures, Gaussian boson sampling is uniquely testable at all scales. Several large, pioneering quantum computing (QC) experiments have been carried out to investigate quantum advantage. Here, we introduce a highly scalable but classical algorithm that can solve GBS approximately. Our numerical simulation of the output count data is closer to the exact solution than current experiments up to 1152 modes. This algorithm outperforms all previous classical, approximate algorithms and scales efficiently to larger experiments. Our results show that effects beyond losses can cause the errors that allow classical simulability. This work will lead to more precise algorithms and is a step towards understanding how QC quantum advantage is affected by the underlying physics.
Achieving a quantum computational advantage regime, and thus providing evidence against the extended Church-Turing thesis, remains one of the key challenges of modern science. Boson sampling seems to be a very promising platform in this regard, but to be confident of attaining the advantage regime, one must provide evidence of operating with a correct boson sampling distribution, rather than with a pathological classically simulatable one. This problem is often called the validation problem, and it poses a major challenge to demonstrating unambiguous quantum advantage. In this work, using the recently proposed wave function network approach, we study the sample space filling behavior with increasing the number of collected samples. We show that due to the intrinsic nature of the boson sampling wave function, its filling behavior can be computationally efficiently distinguished from classically simulated cases. Therefore, we propose a new validation protocol based on the sample space filling analysis and test it for problems of up to 20 photons injected into a 400-mode interferometer. Due to its simplicity and computational efficiency, it can be used among other protocols to validate future experiments to provide more convincing results.
Linear-optical platforms provide a promising route to demonstrate quantum computational advantage, particularly through the boson sampling problem. While a boson sampling system should be large enough to show the quantum advantage, the size of the boson sampling problem is often restricted by experimental constraints. In particular, as a boson sampling system is scaled up, experimental constraints can limit its effective problem size to permit efficient classical simulation. In this paper, we investigate the theoretical scalability bounds for boson sampling systems under practical experimental conditions, including photon loss, mode mismatch, and input state error. We employ non-negativity conditions for phase-space quasiprobability distribution functions to analyze these effects. In addition, we introduce two device-level metrics, the boson sampling score which measures the usable capacity of a given device and the boson sampling volume which provides a common hardware-level benchmark for comparing different platforms and assessing their access to an advantage-relevant problem size regime. Our results provide fundamental insights into the performance of boson sampling systems under realistic experimental conditions and offer practical guidelines for scaling up boson sampling systems.