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 Aaronson and Arkhipov'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 $...
DaftWullie's user avatar
  • 58.1k
7 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 ...
Norbert Schuch's user avatar
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's user avatar
  • 24.9k
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's user avatar
  • 24.9k
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 ...
Craig Gidney's user avatar
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 ...
Frédéric Grosshans's user avatar
4 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 ...
Mark Spinelli's user avatar
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 ...
Alexey Uvarov's user avatar
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 ...
user1271772 No more free time's user avatar
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 ...
Heriotic's user avatar
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 ...
Paul Nation's user avatar
  • 2,239
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 ...
Mark Spinelli's user avatar
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, ...
user1271772 No more free time's user avatar
2 votes
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 ...
Manuel Algaba's user avatar
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 ...
Catalina's user avatar
  • 151
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's user avatar
  • 24.9k
1 vote

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

Just a couple of more comments to expand on the already thorough answers. Initially relating to the error associated with the calculation of the permanent, much of the theory of the complexity of ...
Mark Spinelli's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible