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:2204.08389 · Physical Review Research

Boson sampling for generalized bosons

En-Jui Kuo, Yijia Xu, Dominik Hangleiter, Andrey Grankin, Mohammad Hafezi

Published Nov 14, 2022• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevresearch.4.043096

Related papers

Scalable Implementation of Boson Sampling with Trapped Ions

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

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.

arXiv:1310.4860•Physical Review Letters•Feb 6, 2014•88 citations

Gaussian Boson Sampling

Craig S. Hamilton, Regina Kruse, Linda Sansoni +3 more

Boson sampling has emerged as a tool to explore the advantages of quantum over classical computers as it does not require universal control over the quantum system, which favors current photonic experimental platforms. Here, we introduce Gaussian Boson sampling, a classically hard-to-solve problem that uses squeezed states as a nonclassical resource. We relate the probability to measure specific photon patterns from a general Gaussian state in the Fock basis to a matrix function called the Hafnian, which answers the last remaining question of sampling from Gaussian states. Based on this result, we design Gaussian Boson sampling, a #P hard problem, using squeezed states. This demonstrates that Boson sampling from Gaussian states is possible, with significant advantages in the photon generation probability, compared to existing protocols.

arXiv:1612.01199•Physical Review Letters•Oct 23, 2017•503 citations

Gaussian boson sampling using threshold detectors

Nicolás Quesada, Juan Miguel Arrazola, Nathan Killoran

We study what is arguably the most experimentally appealing boson sampling architecture: Gaussian states sampled with threshold detectors. We show that, in this setting, the probability of observing a given outcome is related to a matrix function that we name the Torontonian, which plays an analogous role to the permanent or the Hafnian in other models. We also prove that, provided that the probability of observing two or more photons in a single output mode is sufficiently small, our model remains intractable to simulate classically under standard complexity-theoretic conjectures. Finally, we leverage the mathematical simplicity of the model to introduce a physically motivated, exact sampling algorithm for all boson sampling models that employ Gaussian states and threshold detectors.

arXiv:1807.01639•Physical Review A•Dec 18, 2018•120 citations

Boson sampling with photons of arbitrary spectral structure

Peter P. Rohde

Boson sampling has attracted much interest as a simplified approach to implementing a subset of optical quantum computing. Boson sampling requires indistinguishable photons, but far fewer of them than universal optical quantum computing architectures. In reality, photons are never indistinguishable, and exhibit a rich spectral structure. Here we consider the operation of boson sampling with photons of arbitrary spectral structure and relate the sampling statistics of the device to matrix permanents. This sheds light on the computational complexity of different regimes of the photons' spectral characteristics, and provides very general results for the operation of linear optics interferometers in the presence of partially distinguishable photons. Our results apply to both the cases of spectrally resolving and nonspectrally resolving detectors.

arXiv:1410.3979•Physical Review A•Jan 8, 2015•33 citations

Gate-based emulation of boson sampling using photonic qubits

Aastha P. Zalone, S. P. Dinesh, C. M. Chandrashekar

Boson sampling arising from multiphoton interference in linear-optical networks is a prominent non-universal model for quantum computation. Here, by encoding the multi-qubit state to bosonic Fock state, we present a scalable quantum-circuit framework for simulating boson sampling on a universal quantum computing platform. Beginning with balanced beam-splitter transformations on the single- and two-photon sectors, we derive equivalent quantum-circuit implementations and unify them within a common Hilbert-space representation using an ancilla-assisted encoding. This construction is then generalized to arbitrary interferometers by replacing each optical beam splitter with a repeating quantum-circuit unit that selectively acts only within the relevant local interference subspace, requiring $N+1$ qubits for a two-photon $N$-mode interferometer and a linear-overhead subspace-identification procedure. Using this framework, gate-based quantum circuit for a four-mode boson-sampling circuit is developed and experimentally implemented on a four-qubit gate-based photonic qubit system. The qubit framework for emulating boson sampling of $n-$photons in $m-$mode will be useful to solve a broad class of sampling complexity problem on a gate-based quantum computers.

quant-pharXiv:2608.09509•Aug 11, 2026•0 citations

Computing matrix permanent with collective boson operators

Joonsuk Huh

Computing permanents of matrices are known to be a classically hard problem that the computational cost grows exponentially with the size of the matrix increases. So far, there exist a few classical algorithms to compute the matrix permanents in deterministic and in randomized ways. By exploiting the series expansion of products of boson operators regarding collective boson operators, a generalized algorithm for computing permanents is developed that the algorithm can handle the arbitrary matrices with repeated columns and rows. In a particular case, the formula is reduced to Glynn's form. Not only the algorithm can be used for a deterministic direct calculation of the matrix permanent but also can be expressed as a sampling problem like Gurvits's randomized algorithm.

•May 27, 2016•0 citations
We introduce the notion of ``generalized bosons'' whose exchange statistics resemble those of bosons, but the local bosonic commutator [a,a\ifmmode†\else\textdagger\fi]=1[a,{a}^{\ifmmode\dagger\else\textdagger\fi{}}]=1[a,a\ifmmode†\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.
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.
Boson sampling has emerged as a tool to explore the advantages of quantum over classical computers as it does not require universal control over the quantum system, which favors current photonic experimental platforms. Here, we introduce Gaussian Boson sampling, a classically hard-to-solve problem that uses squeezed states as a nonclassical resource. We relate the probability to measure specific photon patterns from a general Gaussian state in the Fock basis to a matrix function called the Hafnian, which answers the last remaining question of sampling from Gaussian states. Based on this result, we design Gaussian Boson sampling, a #P hard problem, using squeezed states. This demonstrates that Boson sampling from Gaussian states is possible, with significant advantages in the photon generation probability, compared to existing protocols.
We study what is arguably the most experimentally appealing boson sampling architecture: Gaussian states sampled with threshold detectors. We show that, in this setting, the probability of observing a given outcome is related to a matrix function that we name the Torontonian, which plays an analogous role to the permanent or the Hafnian in other models. We also prove that, provided that the probability of observing two or more photons in a single output mode is sufficiently small, our model remains intractable to simulate classically under standard complexity-theoretic conjectures. Finally, we leverage the mathematical simplicity of the model to introduce a physically motivated, exact sampling algorithm for all boson sampling models that employ Gaussian states and threshold detectors.
Boson sampling has attracted much interest as a simplified approach to implementing a subset of optical quantum computing. Boson sampling requires indistinguishable photons, but far fewer of them than universal optical quantum computing architectures. In reality, photons are never indistinguishable, and exhibit a rich spectral structure. Here we consider the operation of boson sampling with photons of arbitrary spectral structure and relate the sampling statistics of the device to matrix permanents. This sheds light on the computational complexity of different regimes of the photons' spectral characteristics, and provides very general results for the operation of linear optics interferometers in the presence of partially distinguishable photons. Our results apply to both the cases of spectrally resolving and nonspectrally resolving detectors.
Boson sampling arising from multiphoton interference in linear-optical networks is a prominent non-universal model for quantum computation. Here, by encoding the multi-qubit state to bosonic Fock state, we present a scalable quantum-circuit framework for simulating boson sampling on a universal quantum computing platform. Beginning with balanced beam-splitter transformations on the single- and two-photon sectors, we derive equivalent quantum-circuit implementations and unify them within a common Hilbert-space representation using an ancilla-assisted encoding. This construction is then generalized to arbitrary interferometers by replacing each optical beam splitter with a repeating quantum-circuit unit that selectively acts only within the relevant local interference subspace, requiring N+1N+1N+1 qubits for a two-photon NNN-mode interferometer and a linear-overhead subspace-identification procedure. Using this framework, gate-based quantum circuit for a four-mode boson-sampling circuit is developed and experimentally implemented on a four-qubit gate-based photonic qubit system. The qubit framework for emulating boson sampling of n−n-n−photons in m−m-m−mode will be useful to solve a broad class of sampling complexity problem on a gate-based quantum computers.
Computing permanents of matrices are known to be a classically hard problem that the computational cost grows exponentially with the size of the matrix increases. So far, there exist a few classical algorithms to compute the matrix permanents in deterministic and in randomized ways. By exploiting the series expansion of products of boson operators regarding collective boson operators, a generalized algorithm for computing permanents is developed that the algorithm can handle the arbitrary matrices with repeated columns and rows. In a particular case, the formula is reduced to Glynn's form. Not only the algorithm can be used for a deterministic direct calculation of the matrix permanent but also can be expressed as a sampling problem like Gurvits's randomized algorithm.