9
votes
Is it possible to "calculate" the absolute value of a permanent using Boson Sampling?
It appears to be true, up to a point. As I read Scott Aaronson's paper, it says that if you start with 1 photon in each of the first $M$ modes of an interferometer, and find the probability $P_S$ that ...
- 52.3k
7
votes
Accepted
What about BosonSampling can be publicly verified?
About the need of boson sampling verification
First of all, let me point out that it is not a strict necessity to verify the output of a boson sampler. By this, I don't mean to say that it is not ...
glS♦
- 21.7k
7
votes
Is it possible to "calculate" the absolute value of a permanent using Boson Sampling?
You cannot efficiently recover the absolute values of the amplitudes, but if you allow for arbitrary many samples, then you can estimate them to whatever degree of accuracy you like.
More ...
glS♦
- 21.7k
6
votes
Accepted
CS conjecture that Quantum Computer cannot solve NP-complete problems, but Boson Samplers do a #P-hard problem. How is it?
Boson sampling samples from a distribution, but does not compute the full distribution. While computing the distribution is linked to computing permanents, which is #P-hard, we would expect that ...
- 5,443
6
votes
Accepted
What is the HOG test and how would it help proving quantum supremacy?
There are a couple variants of the HOG test.
"Old HOG" computed the proportion of unique samples whose probability is larger than the median probability of the distribution. It then compares that ...
- 30.2k
4
votes
What about BosonSampling can be publicly verified?
Just a small complement to @gIS excellent answer: I know of several people (including myself) interested on the public verification aspect. As far as I know, all attempts have failed, hence the lack ...
3
votes
Are there practical uses for boson sampling?
There is a number of techniques that use Gaussian boson sampling for approximate solution of some practical problems:
https://iopscience.iop.org/article/10.1088/2058-9565/ab8504/meta
For example, some ...
- 664
3
votes
How big is the Hilbert space of a boson sampling experiment?
It was frustrating to read that Wikipedia page. Rather than explaining every single problem with it, I'll only mention the top three problems in the single paragraph that you quoted (if there's this ...
- 12.8k
3
votes
What are known applications of quantum sampling?
The two main classes of sampling problems demonstrating quantum supremacy are BosonSampling and IQP which are intermediate models of optical and qubit based quantum information processing ...
- 76
3
votes
CS conjecture that Quantum Computer cannot solve NP-complete problems, but Boson Samplers do a #P-hard problem. How is it?
This is a well-framed question that highlights subtleties about what is known and unknown on the strengths and limitations of quantum computers.
Initially, it is completely consistent with what we ...
- 9,346
2
votes
Is Gaussian boson sampling (used for showing quantum advantage) a subcategory of the continuous variable approach?
@gIS's comment effectively answers the question, but to provide a bit more detail Aaronson at shtetl-optimized has a nice blog post on the Gaussian Boson Sampling approach of USTC, contrasting it with ...
- 9,346
2
votes
Commutation of bosonic operators on finite Hilbert space
The reason for this is because when you truncate the Hilbert space, applying the raising operator on the highest state raises you out of the Hilbert space, ie it gives a zero vector. Thus the ...
- 2,209
2
votes
What is the relationship between the size of the Hilbert space for boson sampling and the complexity of classical simulating it?
"What is the relationship between the size of the Hilbert space for boson sampling and the complexity of classical simulating it?"
You are correct that for $n$ output photons and $m$ modes, ...
- 12.8k
1
vote
Accepted
Are indistinguishable bosons and fermions computationally equivalent to distinguishable qubits?
Indeed, there are some works in this direction that show the interrelation between fermions, bosons and qubits. Of course, you can consider the seminal work of Jordan and Wigner that maps operators ...
- 116
1
vote
Accepted
I was solving matrix of beam splitter in python but got stuck in understanding the library
A beamsplitter gates takes two parameters, and acts on two modes. The matrix that represents the gate is a 2x2 unitary. In this line you're calculating the unitary for the second 'column' in the ...
- 131
1
vote
Accepted
How many qubits would be needed to do boson sampling in Qiskit?
I'm not sure if this is what you're looking for, but you can always describe the evolution of a many-boson system as the evolution of a set of qudits in the standard "kets and unitaries" ...
glS♦
- 21.7k
Only top scored, non community-wiki answers of a minimum length are eligible