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

Physical Review Letters

Experimental Boson Sampling Enabling Cryptographic One-Way Function

Xiao‐Wei Wang, Wen-Hao Zhou, Yu-Xuan Fu, Jun Gao, Yong‐Heng Lu, Yi-Jun Chang, Lu‐Feng Qiao, Ruo-Jing Ren, Ze-Kun Jiang, Zhi‐Qiang Jiao, Georgios M. Nikolopoulos, Xian‐Min Jin

Published Feb 9, 2023• 5 citations
Publisher

Abstract

Boson sampling is a computational problem, which is commonly believed to be a representative paradigm for attaining the milestone of quantum advantage. So far, massive efforts have been made to the experimental large-scale boson sampling for demonstrating this milestone, while further applications of the machines remain a largely unexplored area. Here, we investigate experimentally the efficiency and security of a cryptographic one-way function that relies on coarse-grained boson sampling, in the framework of a photonic boson-sampling machine fabricated by a femtosecond laser direct writing technique. Our findings demonstrate that the implementation of the function requires moderate sample sizes, which can be over 4 orders of magnitude smaller than the ones predicted by the Chernoff bound; whereas for numbers of photons n≥3 and bins d∼poly(m,n), the same output of the function cannot be generated by nonboson samplers. Our Letter is the first experimental study that deals with the potential applications of boson sampling in the field of cryptography and paves the way toward additional studies in this direction.

DOI
10.1103/physrevlett.130.060802

Related papers

Decision and function problems based on boson sampling

Georgios M. Nikolopoulos, Thomas Brougham

Boson sampling is a mathematical problem that is strongly believed to be intractable for classical computers, whereas passive linear interferometers can produce samples efficiently. So far, the problem remains a computational curiosity, and the possible usefulness of boson-sampling devices is mainly limited to the proof of quantum supremacy. The purpose of this work is to investigate whether boson sampling can be used as a resource of decision and function problems that are computationally hard, and may thus have cryptographic applications. After the definition of a rather general theoretical framework for the design of such problems, we discuss their solution by means of a brute-force numerical approach, as well as by means of nonboson samplers. Moreover, we estimate the sample sizes required for their solution by passive linear interferometers, and it is shown that they are independent of the size of the Hilbert space.

arXiv:1607.02987•Physical Review A•Jul 11, 2016•20 citations

Experimental loopback boson sampling

Yu. A. Biriukov, R. D. Morozov, K. I. Okhlopkov +15 more

We present an experimental demonstration of boson sampling enhanced by optical feedback lines, a novel approach that introduces temporal correlations among photons to amplify computational complexity. We utilize a 25-mode femtosecond laser-written interferometer with five output channels connected to five input channels to create correlations between consecutive photon arrival events. We have reconstructed the unitary matrix of the chip and have conducted Bayesian analysis to validate the sampler and confirm that the system exhibits behavior distinct from standard boson sampling. We also built a theoretical description of the system based on the transformation of annihilation operators and, using it, delivered the structure of the transmission matrix and the complexity of our boson sampler in terms of a conventional boson sampler. This work advances photonic quantum computing by demonstrating a resource-efficient method to increase sampling complexity, paving the way for scalable demonstration of quantum advantage with single photons.

quant-pharXiv:2511.09382•Optica Quantum•Nov 13, 2025•0 citations

Efficient classical algorithm for estimating linear statistics of Boson Sampling

Benoit Seron, Hugo Thomas, Eduardo Araujo +3 more

Boson Sampling is a prominent candidate for the demonstration of quantum computational advantage but it remains unclear whether a large-scale boson sampler can find useful computational applications. The challenge is that to use a boson sampler to estimate, for example, a physical observable, it is necessary to coarse grain the outcome distribution, owing to the exponential size of the outcome space and the anti-concentration properties of the Boson Sampling distribution. In this work, we analyse the complexity of a specific type of coarse-graining of Boson Sampling distributions based on linear functions of the output photon occupation numbers, which we refer to as linear statistics. We present an efficient classical algorithm for approximating linear statistics of boson samplers within additive error for different kinds of input states, such as Fock states and squeezed states. This allows us to unify in the same framework recent results on efficient quantum-inspired classical algorithms for simulating molecular vibronic spectra, or efficient classical approximations of coarse-grained distributions based on detector binning. Additionally, we show how our algorithm can be used to classically evaluate a proposed one-way function based on Boson Sampling, while other proposals for cryptographic applications escape our classical simulation techniques. We leave open the question of classical simulability of non-linear statistics and connect it to the problem of computing transition amplitudes of linear-optical circuits with one layer of interactions.

quant-pharXiv:2609.35447•Sep 29, 2026•0 citations

Timestamp boson sampling

Wenhao Zhou, Jun Gao, Zhi‐Qiang Jiao +7 more

Quantum advantage, benchmarking the computational power of quantum machines outperforming all classical computers in a specific task, represents a crucial milestone in developing quantum computers and has been driving different physical implementations since the concept was proposed. A boson sampling machine, an analog quantum computer that only requires multiphoton interference and single-photon detection, is considered to be a promising candidate to reach this goal. However, the probabilistic nature of photon sources and the inevitable loss in evolution network make the execution time exponentially increasing with the problem size. Here, we propose and experimentally demonstrate a timestamp boson sampling scheme that can effectively reduce the execution time for any problem size. By developing a time-of-flight storage technique with a precision up to picosecond level, we are able to detect and record the complete time information of 30 individual modes out of a large-scale 3D photonic chip. We perform the three-photon injection and one external trigger experiment to demonstrate that the timestamp protocol works properly and effectively reduce the execution time. We further verify that timestamp boson sampler is distinguished from other samplers in the case of limited datasets through the three heralded single photons injection experiment. The timestamp protocol can speed up the sampling process, which can be widely applied in multiphoton experiments at low-sampling rate. The approach associated with newly exploited resource from time information can boost all the count-rate-limited experiments, suggesting an emerging field of timestamp quantum optics.

arXiv:2009.03327•Applied Physics Reviews•Sep 1, 2022•14 citations

Physical Unclonable Functions with Boson Sampling

Juan Carlos García-Escartín

Boson sampling is a problem for which quantum devices could prove to go beyond classical computing using only linear optics and photon preparation and counting. While theoretically important, there is a lack of practical applications for this task. This paper presents a way to turn any boson sampling device for which there are certain fabrication limits into a physically unclonable function which could be used in identification systems and other security protocols. For a minimum fabrication error, there are scenarios for which the photon distribution at the output of two different devices has a minimum distance and they can be told apart. When compared to classical PUFs these linear optical tokens have the advantage that, for the right choice of parameters, there is a computational guarantee that no classical computer can simulate the output. The paper describes the basic limitations of boson sampling which allow these results and gives a possible choice for a challenge-response identification protocol. This gives a direct application of boson sampling which could be simpler than solving the general problem.

arXiv:1911.08417•Nov 19, 2019•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
Boson sampling is a computational problem, which is commonly believed to be a representative paradigm for attaining the milestone of quantum advantage. So far, massive efforts have been made to the experimental large-scale boson sampling for demonstrating this milestone, while further applications of the machines remain a largely unexplored area. Here, we investigate experimentally the efficiency and security of a cryptographic one-way function that relies on coarse-grained boson sampling, in the framework of a photonic boson-sampling machine fabricated by a femtosecond laser direct writing technique. Our findings demonstrate that the implementation of the function requires moderate sample sizes, which can be over 4 orders of magnitude smaller than the ones predicted by the Chernoff bound; whereas for numbers of photons n≥3 and bins d∼poly(m,n), the same output of the function cannot be generated by nonboson samplers. Our Letter is the first experimental study that deals with the potential applications of boson sampling in the field of cryptography and paves the way toward additional studies in this direction.
Boson sampling is a mathematical problem that is strongly believed to be intractable for classical computers, whereas passive linear interferometers can produce samples efficiently. So far, the problem remains a computational curiosity, and the possible usefulness of boson-sampling devices is mainly limited to the proof of quantum supremacy. The purpose of this work is to investigate whether boson sampling can be used as a resource of decision and function problems that are computationally hard, and may thus have cryptographic applications. After the definition of a rather general theoretical framework for the design of such problems, we discuss their solution by means of a brute-force numerical approach, as well as by means of nonboson samplers. Moreover, we estimate the sample sizes required for their solution by passive linear interferometers, and it is shown that they are independent of the size of the Hilbert space.
We present an experimental demonstration of boson sampling enhanced by optical feedback lines, a novel approach that introduces temporal correlations among photons to amplify computational complexity. We utilize a 25-mode femtosecond laser-written interferometer with five output channels connected to five input channels to create correlations between consecutive photon arrival events. We have reconstructed the unitary matrix of the chip and have conducted Bayesian analysis to validate the sampler and confirm that the system exhibits behavior distinct from standard boson sampling. We also built a theoretical description of the system based on the transformation of annihilation operators and, using it, delivered the structure of the transmission matrix and the complexity of our boson sampler in terms of a conventional boson sampler. This work advances photonic quantum computing by demonstrating a resource-efficient method to increase sampling complexity, paving the way for scalable demonstration of quantum advantage with single photons.
Boson Sampling is a prominent candidate for the demonstration of quantum computational advantage but it remains unclear whether a large-scale boson sampler can find useful computational applications. The challenge is that to use a boson sampler to estimate, for example, a physical observable, it is necessary to coarse grain the outcome distribution, owing to the exponential size of the outcome space and the anti-concentration properties of the Boson Sampling distribution. In this work, we analyse the complexity of a specific type of coarse-graining of Boson Sampling distributions based on linear functions of the output photon occupation numbers, which we refer to as linear statistics. We present an efficient classical algorithm for approximating linear statistics of boson samplers within additive error for different kinds of input states, such as Fock states and squeezed states. This allows us to unify in the same framework recent results on efficient quantum-inspired classical algorithms for simulating molecular vibronic spectra, or efficient classical approximations of coarse-grained distributions based on detector binning. Additionally, we show how our algorithm can be used to classically evaluate a proposed one-way function based on Boson Sampling, while other proposals for cryptographic applications escape our classical simulation techniques. We leave open the question of classical simulability of non-linear statistics and connect it to the problem of computing transition amplitudes of linear-optical circuits with one layer of interactions.
Quantum advantage, benchmarking the computational power of quantum machines outperforming all classical computers in a specific task, represents a crucial milestone in developing quantum computers and has been driving different physical implementations since the concept was proposed. A boson sampling machine, an analog quantum computer that only requires multiphoton interference and single-photon detection, is considered to be a promising candidate to reach this goal. However, the probabilistic nature of photon sources and the inevitable loss in evolution network make the execution time exponentially increasing with the problem size. Here, we propose and experimentally demonstrate a timestamp boson sampling scheme that can effectively reduce the execution time for any problem size. By developing a time-of-flight storage technique with a precision up to picosecond level, we are able to detect and record the complete time information of 30 individual modes out of a large-scale 3D photonic chip. We perform the three-photon injection and one external trigger experiment to demonstrate that the timestamp protocol works properly and effectively reduce the execution time. We further verify that timestamp boson sampler is distinguished from other samplers in the case of limited datasets through the three heralded single photons injection experiment. The timestamp protocol can speed up the sampling process, which can be widely applied in multiphoton experiments at low-sampling rate. The approach associated with newly exploited resource from time information can boost all the count-rate-limited experiments, suggesting an emerging field of timestamp quantum optics.
Boson sampling is a problem for which quantum devices could prove to go beyond classical computing using only linear optics and photon preparation and counting. While theoretically important, there is a lack of practical applications for this task. This paper presents a way to turn any boson sampling device for which there are certain fabrication limits into a physically unclonable function which could be used in identification systems and other security protocols. For a minimum fabrication error, there are scenarios for which the photon distribution at the output of two different devices has a minimum distance and they can be told apart. When compared to classical PUFs these linear optical tokens have the advantage that, for the right choice of parameters, there is a computational guarantee that no classical computer can simulate the output. The paper describes the basic limitations of boson sampling which allow these results and gives a possible choice for a challenge-response identification protocol. This gives a direct application of boson sampling which could be simpler than solving the general problem.
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.