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

International Conference on Natural Computation (ICNC)

Quantum Boson-Sampling Machine

Yong Liu, Junjie Wu, Xun Yi

Published Aug 1, 2015• 1 citation
Publisher

Abstract

In the Post-Moore law era, Quantum computing, as a novel promising computing technology, is paid great attention to, since quantum algorithms are able to offer exponential speed-up over the classical ones. However, despite the various means for the implementation of a universal quantum computer, it's desperately hard to build one. Fortunately, a computing model called Boson-Sampling is able to show the great power of quantum computing. The device that conducts the simulation process of Boson-Sampling based on quantum computing is called Quantum Boson-Sampling Machine (QBSM) while this simulation on a classical computer is intractable. In this paper, we introduce the boson-sampling process, analyze the difficulty of Boson-Sampling on classical computing, describe the advantages of Boson-Sampling, list the resent physical experiments that implemented QBSMs, and discuss the further research of Boson-Sampling.

DOI
10.1109/icnc.2015.7378023

Related papers

An Introduction to Boson-Sampling

Bryan T. Gard, Keith R. Motes, Jonathan P. Olson +2 more

Boson-sampling is a simplified model for quantum computing that may hold the key to implementing the first ever post-classical quantum computer. Boson-sampling is a non-universal quantum computer that is significantly more straightforward to build than any universal quantum computer proposed so far. We begin this chapter by motivating boson-sampling and discussing the history of linear optics quantum computing. We then summarize the boson-sampling formalism, discuss what a sampling problem is, explain why boson-sampling is easier than linear optics quantum computing, and discuss the Extended Church-Turing thesis. Next, sampling with other classes of quantum optical states is analyzed. Finally, we discuss the feasibility of building a boson-sampling device using existing technology.

arXiv:1406.6767•WORLD SCIENTIFIC eBooks•Jun 28, 2015•26 citations

An introduction to Boson-sampling

Gard, BT, Motes, KR, Olson, JP +2 more

© 2010 by World Scientific Publishing Co. Pte. Ltd. All rights reserved. Boson-sampling is a simplified model for quantum computing that may hold the key to implementing the first ever post-classical quantum computer. Boson-sampling is a non-universal quantum computer that is significantly more straightforward to build than any universal quantum computer proposed so far. We begin this chapter by motivating boson-sampling and discussing the history of linear optics quantum computing. We then summarize the boson-sampling formalism, discuss what a sampling problem is, explain why boson-sampling is easier than linear optics quantum computing, and discuss the Extended Church-Turing thesis. Next, sampling with other classes of quantum optical states is analyzed. Finally, we discuss the feasibility of building a boson-sampling device using existing technology.

•Jan 1, 2015•56 citations

Gaussian boson sampling: Benchmarking quantum advantage

Ned Goodman, Alexander S. Dellios, Margaret D. Reid +1 more

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.

quant-pharXiv:2604.12330•Apr 15, 2026•0 citations

Routes Towards Optical Quantum Technology --- New Architectures and Applications

Keith R. Motes

As this century unfolds we will witness the rise of the quantum computer. A quantum computer is a device that utilizes the laws of one of the most fundamental theories of physics— quantum mechanics. By utilizing properties of quantum mechanics a quantum computer is able to perform certain information processing tasks much more effciently than an ordinary classical computer. The last century of modern society was revolutionized by some of the simplest ideas in quantum mechanics like energy quantization and quantum tunnelling, which led to technologies like the laser and the transistor. We can expect to see additional technological revolutions occur in this century since we are beginning to build technologies with some of the more complex properties of quantum mechanics such as quantum entanglement and quantum superposition. These quantum effects make more radical technologies like the quantum computer possible. This thesis is based upon the work I have done during my PhD candidature at Macquarie University. In this work we develop quantum technologies that are directed towards realising a quantum computer. Specifically, we have made many theoretical advancements in a type of quantum information processing protocol called Boson Sampling. This device effciently simulates the interaction of quantum particles called bosons, which no classical computer can effciently simulate. In this thesis we explore quantum random walks, which are the basis of how the bosons in Boson Sampling interfere with each other. We explore implementing BosonSampling using the most readily available photon source technology. We invented a completely new architecture which can implement Boson Sampling in time rather than space and has since been used to make the worlds largest Boson Sampling experiment ever performed. We look at variations to the traditional Boson Sampling architecture by considering other quantum states of light. We show a worlds first application inspired by Boson Sampling in quantum metrology where measurements may be made more accurately than with any classical method. Lastly, dealing with Boson Sampling, we look at reformulating the formalism of Boson Sampling using a quantum optics approach. In addition, but not related to BosonSampling, we show a protocol for effciently generating large-photon Fock states, which are a type of quantum state of light, that are useful for quantum computation. Also, we show a method for generating a specific quantum state of light that is useful for quantum error correction — an essential component of realising a quantum computer — by coupling together light and atoms.

arXiv:1703.05309•Mar 15, 2017•0 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

Photonic implementation of boson sampling: a review

Daniel J. Brod, Ernesto F. Galvão, Andrea Crespi +3 more

Boson sampling is a computational problem that has recently been proposed as a candidate to obtain an unequivocal quantum computational advantage. The problem consists in sampling from the output distribution of indistinguishable bosons in a linear interferometer. There is strong evidence that such an experiment is hard to classically simulate, but it is naturally solved by dedicated photonic quantum hardware, comprising single photons, linear evolution, and photodetection. This prospect has stimulated much effort resulting in the experimental implementation of progressively larger devices. We review recent advances in photonic boson sampling, describing both the technological improvements achieved and the future challenges. We also discuss recent proposals and implementations of variants of the original problem, theoretical issues occurring when imperfections are considered, and advances in the development of suitable techniques for validation of boson sampling experiments. We conclude by discussing the future application of photonic boson sampling devices beyond the original theoretical scope.

Advanced Photonics•May 9, 2019•160 citations
In the Post-Moore law era, Quantum computing, as a novel promising computing technology, is paid great attention to, since quantum algorithms are able to offer exponential speed-up over the classical ones. However, despite the various means for the implementation of a universal quantum computer, it's desperately hard to build one. Fortunately, a computing model called Boson-Sampling is able to show the great power of quantum computing. The device that conducts the simulation process of Boson-Sampling based on quantum computing is called Quantum Boson-Sampling Machine (QBSM) while this simulation on a classical computer is intractable. In this paper, we introduce the boson-sampling process, analyze the difficulty of Boson-Sampling on classical computing, describe the advantages of Boson-Sampling, list the resent physical experiments that implemented QBSMs, and discuss the further research of Boson-Sampling.
Boson-sampling is a simplified model for quantum computing that may hold the key to implementing the first ever post-classical quantum computer. Boson-sampling is a non-universal quantum computer that is significantly more straightforward to build than any universal quantum computer proposed so far. We begin this chapter by motivating boson-sampling and discussing the history of linear optics quantum computing. We then summarize the boson-sampling formalism, discuss what a sampling problem is, explain why boson-sampling is easier than linear optics quantum computing, and discuss the Extended Church-Turing thesis. Next, sampling with other classes of quantum optical states is analyzed. Finally, we discuss the feasibility of building a boson-sampling device using existing technology.
© 2010 by World Scientific Publishing Co. Pte. Ltd. All rights reserved. Boson-sampling is a simplified model for quantum computing that may hold the key to implementing the first ever post-classical quantum computer. Boson-sampling is a non-universal quantum computer that is significantly more straightforward to build than any universal quantum computer proposed so far. We begin this chapter by motivating boson-sampling and discussing the history of linear optics quantum computing. We then summarize the boson-sampling formalism, discuss what a sampling problem is, explain why boson-sampling is easier than linear optics quantum computing, and discuss the Extended Church-Turing thesis. Next, sampling with other classes of quantum optical states is analyzed. Finally, we discuss the feasibility of building a boson-sampling device using existing technology.
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.
As this century unfolds we will witness the rise of the quantum computer. A quantum computer is a device that utilizes the laws of one of the most fundamental theories of physics— quantum mechanics. By utilizing properties of quantum mechanics a quantum computer is able to perform certain information processing tasks much more effciently than an ordinary classical computer. The last century of modern society was revolutionized by some of the simplest ideas in quantum mechanics like energy quantization and quantum tunnelling, which led to technologies like the laser and the transistor. We can expect to see additional technological revolutions occur in this century since we are beginning to build technologies with some of the more complex properties of quantum mechanics such as quantum entanglement and quantum superposition. These quantum effects make more radical technologies like the quantum computer possible. This thesis is based upon the work I have done during my PhD candidature at Macquarie University. In this work we develop quantum technologies that are directed towards realising a quantum computer. Specifically, we have made many theoretical advancements in a type of quantum information processing protocol called Boson Sampling. This device effciently simulates the interaction of quantum particles called bosons, which no classical computer can effciently simulate. In this thesis we explore quantum random walks, which are the basis of how the bosons in Boson Sampling interfere with each other. We explore implementing BosonSampling using the most readily available photon source technology. We invented a completely new architecture which can implement Boson Sampling in time rather than space and has since been used to make the worlds largest Boson Sampling experiment ever performed. We look at variations to the traditional Boson Sampling architecture by considering other quantum states of light. We show a worlds first application inspired by Boson Sampling in quantum metrology where measurements may be made more accurately than with any classical method. Lastly, dealing with Boson Sampling, we look at reformulating the formalism of Boson Sampling using a quantum optics approach. In addition, but not related to BosonSampling, we show a protocol for effciently generating large-photon Fock states, which are a type of quantum state of light, that are useful for quantum computation. Also, we show a method for generating a specific quantum state of light that is useful for quantum error correction — an essential component of realising a quantum computer — by coupling together light and atoms.
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 is a computational problem that has recently been proposed as a candidate to obtain an unequivocal quantum computational advantage. The problem consists in sampling from the output distribution of indistinguishable bosons in a linear interferometer. There is strong evidence that such an experiment is hard to classically simulate, but it is naturally solved by dedicated photonic quantum hardware, comprising single photons, linear evolution, and photodetection. This prospect has stimulated much effort resulting in the experimental implementation of progressively larger devices. We review recent advances in photonic boson sampling, describing both the technological improvements achieved and the future challenges. We also discuss recent proposals and implementations of variants of the original problem, theoretical issues occurring when imperfections are considered, and advances in the development of suitable techniques for validation of boson sampling experiments. We conclude by discussing the future application of photonic boson sampling devices beyond the original theoretical scope.