New answers tagged complexity-theory
1
Here is one example of exponential speedup. It is to find eigenvalues and eigenvectors of a local Hamiltonian using the quantum fast Fourier transform Daniel S. Abrams, Seth Lloyd, A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors.
2
Boaz Barak has a lovely essay on various hypothetical worlds with quantum computers. In particular, he calls your world where NP$\subseteq$BQP "popscitopia", and provides:
...in popscitopia quantum computers can be built, and NP $\subseteq$ BQP. This is the world that is described by some popular accounts of quantum computers as being able to “...
3
Time complexity in itself does not care how you solve the problem. If you have a solution on a classical machine that takes $O(n)$ and a quantum one that also takes $O(n)$ then both are equally good complexity-wise (practically: probably the classical one being cheaper, more pragmatic etc.)
If you have a solution that is $O(n^4)$ on a quantum or classical ...
3
"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, the size of the Hilbert space is:
$$
n + m -1 \choose n \tag{1}
$$
and that the best currently known classical algorithm for exactly simulating the boson ...
1
Maybe.
Grovers algorithm can definitely be used to reduce the time complexity of NP complete problems to $O(\sqrt{2^n})$ ; which isn't polynomial but is a lot faster. But the relationship between BQP and NP is unknown. For all we know $PH \subseteq BQP$ could be true.
It's thought to be unlikely but we cannot rule it out and in my opinion its useless to ...
0
If an NP-Complete problem is proven to be part of BQP, the whole industry of cryptography will be turned upside-down since the process of mathematically breaking a crypto-system can be expressed as a boolean-SAT problem.
It would become much more difficult to establish secret and secure communication, though not entirely impossible because being able to ...
2
One "dumb" way to speed-up a generic SAT problem would be to use Grover's Algorithm, but that would only give a quadratic speed-up over brute-force. It may the best one can do for some (or many) situations, but this is the most straight-forward thing that comes to mind.
Grover's algorithm is an algorithm that finds the input that makes an oracle ...
Top 50 recent answers are included