New answers tagged

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