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

arXiv:1310.4860 · Physical Review Letters

Scalable Implementation of Boson Sampling with Trapped Ions

Chao Shen, Z. Zhang, L.-M. Duan

Published Feb 6, 2014• 88 citations
arXivHTMLPDF

Abstract

Boson sampling solves a classically intractable problem by sampling from a probability distribution given by matrix permanents. We propose a scalable implementation of boson sampling using local transverse phonon modes of trapped ions to encode the bosons. The proposed scheme allows deterministic preparation and high-efficiency readout of the bosons in the Fock states and universal mode mixing. With the state-of-the-art trapped ion technology, it is feasible to realize boson sampling with tens of bosons by this scheme, which would outperform the most powerful classical computers and constitute an effective disproof of the famous extended Church-Turing thesis.

DOI
10.1103/physrevlett.112.050504

Related papers

Boson sampling for generalized bosons

En-Jui Kuo, Yijia Xu, Dominik Hangleiter +2 more

We introduce the notion of ``generalized bosons'' whose exchange statistics resemble those of bosons, but the local bosonic commutator $[a,{a}^{\ifmmode\dagger\else\textdagger\fi{}}]=1$ is replaced by an arbitrary single-mode operator that is diagonal in the generalized Fock basis. Examples of generalized bosons include boson pairs and spins. We consider the analog of the boson sampling task for these particles and observe that its output probabilities are still given by permanents, so that the results regarding hardness of sampling directly carry over. Finally, we propose implementations of generalized boson sampling in circuit-QED and ion-trap platforms.

arXiv:2204.08389•Physical Review Research•Nov 14, 2022•5 citations

Boson sampling with Gaussian input states: Toward efficient scaling and certification

Raphael A. Abrahão, Arman Mansouri, Austin P. Lund

A universal quantum computer of large 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. Although boson sampling was demonstrated and the threshold to claim quantum computational advantage was achieved, the question of how to scale up boson sampling experiments remains. To make progress with this problem, here we present a practically achievable pathway to scale boson sampling experiments by combining continuous-variable quantum information and temporal encoding. We propose the combination of switchable dual-homodyne and single-photon detections, the temporal loop technique, and scattershot-based boson sampling. We detail the required assumptions for concluding computational hardness for this configuration. Furthermore, this particular combination of techniques moves towards an efficient scaling and certification of boson sampling, all in a single experimental setup.

arXiv:1812.08978•Physical Review A•Nov 26, 2024•1 citation

Boson Sampling with Gaussian input states: efficient scaling and certification.

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. Although Boson Sampling was demonstrated and the threshold to claim quantum computational advantage was achieved, the question on how to scale up Boson Sampling experiments remains. To make progress with this problem, here we present a practically achievable pathway to scale Boson Sampling experiments with current technologies 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 scaling Boson Sampling experiments. Furthermore, this particular combination of techniques permits a single efficient implementation of Boson Sampling and efficient certification in a single experimental setup.

•Nov 29, 2021•0 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

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

Faster classical boson sampling

Peter Clifford, Raphaël Clifford A

Abstract Since its introduction boson sampling has been the subject of intense study in the world of quantum computing. In the context of Fock-state boson sampling, the task is to sample independently from the set of all n × n submatrices built from possibly repeated rows of a larger m × n complex matrix according to a probability distribution related to the permanents of the submatrices. Experimental systems exploiting quantum photonic effects can in principle perform the task at great speed. For classical computing, Aaronson and Arkhipov (2011) showed that exact boson sampling problem cannot be solved in polynomial time unless the polynomial hierarchy collapses to the third level. Indeed for a number of years the fastest known exact classical algorithm ran in O ( m + n − 1 n n 2 n ) time per sample, emphasising the potential speed advantage of quantum computation. The advantage was reduced by Clifford and Clifford (2018), who gave a significantly faster classical solution taking O ( n 2 n + poly ( m , n ) ) time and linear space, matching the complexity of computing the permanent of a single matrix when m is polynomial in n. We continue by presenting an algorithm for Fock boson sampling whose average-case time complexity is much faster when m is proportional to n. In particular, when m = n our algorithm runs in approximately O(n · 1.69 n ) time on average. This result further increases the problem size needed to establish quantum computational advantage via the Fock scheme of boson sampling.

arXiv:2005.04214•Physica Scripta•May 2, 2024•21 citations
Boson sampling solves a classically intractable problem by sampling from a probability distribution given by matrix permanents. We propose a scalable implementation of boson sampling using local transverse phonon modes of trapped ions to encode the bosons. The proposed scheme allows deterministic preparation and high-efficiency readout of the bosons in the Fock states and universal mode mixing. With the state-of-the-art trapped ion technology, it is feasible to realize boson sampling with tens of bosons by this scheme, which would outperform the most powerful classical computers and constitute an effective disproof of the famous extended Church-Turing thesis.
We introduce the notion of ``generalized bosons'' whose exchange statistics resemble those of bosons, but the local bosonic commutator $[a,{a}^{\ifmmode\dagger\else\textdagger\fi{}}]=1$ is replaced by an arbitrary single-mode operator that is diagonal in the generalized Fock basis. Examples of generalized bosons include boson pairs and spins. We consider the analog of the boson sampling task for these particles and observe that its output probabilities are still given by permanents, so that the results regarding hardness of sampling directly carry over. Finally, we propose implementations of generalized boson sampling in circuit-QED and ion-trap platforms.
A universal quantum computer of large 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. Although boson sampling was demonstrated and the threshold to claim quantum computational advantage was achieved, the question of how to scale up boson sampling experiments remains. To make progress with this problem, here we present a practically achievable pathway to scale boson sampling experiments by combining continuous-variable quantum information and temporal encoding. We propose the combination of switchable dual-homodyne and single-photon detections, the temporal loop technique, and scattershot-based boson sampling. We detail the required assumptions for concluding computational hardness for this configuration. Furthermore, this particular combination of techniques moves towards an efficient scaling and certification of boson sampling, all in a single experimental setup.
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. Although Boson Sampling was demonstrated and the threshold to claim quantum computational advantage was achieved, the question on how to scale up Boson Sampling experiments remains. To make progress with this problem, here we present a practically achievable pathway to scale Boson Sampling experiments with current technologies 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 scaling Boson Sampling experiments. Furthermore, this particular combination of techniques permits a single efficient implementation of Boson Sampling and efficient certification in a single experimental setup.
© 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.
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.
Abstract Since its introduction boson sampling has been the subject of intense study in the world of quantum computing. In the context of Fock-state boson sampling, the task is to sample independently from the set of all n × n submatrices built from possibly repeated rows of a larger m × n complex matrix according to a probability distribution related to the permanents of the submatrices. Experimental systems exploiting quantum photonic effects can in principle perform the task at great speed. For classical computing, Aaronson and Arkhipov (2011) showed that exact boson sampling problem cannot be solved in polynomial time unless the polynomial hierarchy collapses to the third level. Indeed for a number of years the fastest known exact classical algorithm ran in O ( m + n − 1 n n 2 n ) time per sample, emphasising the potential speed advantage of quantum computation. The advantage was reduced by Clifford and Clifford (2018), who gave a significantly faster classical solution taking O ( n 2 n + poly ( m , n ) ) time and linear space, matching the complexity of computing the permanent of a single matrix when m is polynomial in n. We continue by presenting an algorithm for Fock boson sampling whose average-case time complexity is much faster when m is proportional to n. In particular, when m = n our algorithm runs in approximately O(n · 1.69 n ) time on average. This result further increases the problem size needed to establish quantum computational advantage via the Fock scheme of boson sampling.