Quantum Computing Stack Exchange
Quantum Computing Stack Exchange

Questions tagged [boson-sampling]

Boson sampling constitutes a restricted model of non-universal quantum computation introduced by S. Aaronson and A. Arkhipov. It consists of sampling from the probability distribution of identical bosons scattered by a linear interferometer. (Wikipedia)

Boson Sampling

Boson sampling constitutes a restricted model of non-universal quantum computation introduced by S. Aaronson and A. Arkhipov. It consists of sampling from the probability distribution of identical bosons scattered by a linear interferometer. Although the problem is well defined for any bosonic particles, its photonic version is currently considered as the most promising platform for a scalable implementation of a boson sampling device, which makes it a non-universal approach to linear optical quantum computing. Moreover, while not universal, the boson sampling scheme is strongly believed to implement a classically hard task using far fewer physical resources than a full linear-optical quantum computing setup. This makes it an outstanding candidate for demonstrating the power of quantum computation in the near term.

Read more on Wikipedia: https://en.wikipedia.org/wiki/Boson_sampling

16 questions
22
votes
3 answers

Is it possible to "calculate" the absolute value of a permanent using Boson Sampling?

In boson sampling, if we start with 1 photon in each of the first $M$ modes of an interferometer, the probability of detecting 1 photon in each output mode is: $|\textrm{Perm}(A)|^2$, where the columns and rows of $A$ are the first $M$ columns of…
user1271772 No more free time
  • 14,286
  • 2
  • 26
  • 76
12
votes
1 answer

How many qubits would be needed to do boson sampling in Qiskit?

In December 2020, there was this claim of quantum advantage/supremacy by a team of UST China using Gaussian boson sampling. Here is the paper and here is an explanatory news article in Nature. To get an idea of how that works, I wanted to try to…
Mauricio
  • 2,426
  • 4
  • 25
9
votes
2 answers

What about BosonSampling can be publicly verified?

Boson Sampling, sometimes stylized as BosonSampling, is an attractive candidate problem to establish quantum supremacy; the engineering problems appear more surmountable than those associated with a Turing-complete quantum computer. However, Boson…
Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83
8
votes
1 answer

Are indistinguishable bosons and fermions computationally equivalent to distinguishable qubits?

From the middle-late decades of the last century, many researchers such as Bennett, Benoif, Deutsch, Feynman, Manin, Wiesner, among others, had some intuition that qubits are computationally more powerful or more interesting than classical…
Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83
7
votes
1 answer

What is the relationship between the size of the Hilbert space for boson sampling and the complexity of classical simulating it?

My intuition is that the fastest classical algorithm for simulating some kind of noiseless quantum sampling process should scale roughly with the dimension of the Hilbert space: you would need to process each amplitude at least once in order to…
tparker
  • 2,939
  • 13
  • 26
7
votes
1 answer

Is Gaussian boson sampling (used for showing quantum advantage) a subcategory of the continuous variable approach?

I read about the photonic QC Jiŭzhāng that showed quantum advantage by Gaussian boson sampling. I read that boson sampling itself is a sub-universal technique of QC (where they use single-photon states as input states). In the paper, the scientists…
ile2N
  • 155
  • 5
6
votes
1 answer

What is the HOG test and how would it help proving quantum supremacy?

Proposed experiments in achieving quantum supremacy, such as with BosonSampling or using random circuits, have been described as using a (not necessarily Turing complete) quantum computer to perform some sampling problem. An example would be to…
Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83
6
votes
2 answers

CS conjecture that Quantum Computer cannot solve NP-complete problems, but Boson Samplers do a #P-hard problem. How is it?

There is something very strange and absurd for me about the power of a quantum computer. Let me briefly states the following facts: Fact 1: theoretical computer scientists believe (very likely to happen) that quantum computer cannot solve…
user777
  • 377
  • 2
  • 8
5
votes
1 answer

How big is the Hilbert space of a boson sampling experiment?

Boson sampling experiments are typically characterized by two key parameters: the number of photons $M$ and the number of modes $N$. A recent experimental demonstration (arXiv:2106.15534) with $M = 113$ and $N = 144$ says that the Hilbert space…
tparker
  • 2,939
  • 13
  • 26
4
votes
0 answers

Boson Sampling with a single beamsplitter

In Boson Sampling as first proposed by Aaronson and Arkhipov in arxiv.org/abs/1011.3245, the interferometer is made up of phase shifters and beamsplitters. As these gates are universal, drawing the interferometer at random (just like in Google's…
Marsl
  • 1,009
  • 7
  • 11
4
votes
0 answers

Is the pfaffian for gaussian fermions what the hafnian is for gaussian bosons?

In some recent papers, e.g. Phys. Rev. Lett. 119, 170501, the problem of gaussian boson sampling is shown to be related to the hafnian of a certain matrix. When applied to the adjacency matrix of a graph, the hafnian gives the number of perfect…
thedude
  • 181
  • 4
4
votes
1 answer

What are known applications of quantum sampling?

I'm inspired by [1] which clearly lays out near term applications of quantum computing: optimization, simulation and sampling. They claim that quantum sampling is likely to be the first application that achieves quantum supremacy "Our calculations…
Derek Lomas
  • 41
  • 2
3
votes
1 answer

Are there practical uses for boson sampling?

Boson sampling is a computation that is not doable on classical machines but quite doable on quantum photonic…
James
  • 551
  • 3
  • 11
2
votes
1 answer

Commutation of bosonic operators on finite Hilbert space

I'm checking this article of R. Somma about quantum simulations https://arxiv.org/abs/quant-ph/0512209 I understand the common commutation relations for creationd and annihilation operators, given by: $$[b_i, b_j^\dagger]|n_1 n_2\dots n_N\rangle =…
Dani
  • 287
  • 2
  • 8
1
vote
0 answers

Can one simulate Gaussian Boson Sampling using Fock Boson Sampling or vice versa?

In Fock Boson Sampling, one starts with a particle-number state $|n_1, ..., n_m\rangle$ of $m$ modes, sends it to an interferometer effecting a unitary operation $U$ on the creation operators, and measures the output. In Gaussian Boson Sampling, the…
Alexey Uvarov
  • 716
  • 5
  • 15
1
2