Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
18 votes
Accepted

Is relation between BQP and QMA resolved?

I haven't looked at the paper carefully, but one thing I noticed is that their proof that BQP $\subsetneqq$ QMA works by their claiming that "bit commitment $\not \in$ BQP" but "bit ...
Peter Shor 's user avatar
8 votes
Accepted

A contradiction in the realm of quantum digital and analog computation

Blum-Shub-Smale machines manage to solve NP-complete problems by using an exponential number of the digits of precision. Nothing that you can do in a physics experiment uses more than thirty digits of ...
Peter Shor 's user avatar
7 votes

Richard Feynman says that all quantum procedures are able to be simulated by quantum computation

Since we don't know the ultimate physical laws of the universe, and we would need to know them (or at least know much more about them than we do now) to prove Feynman's conjecture, his conjecture is ...
Peter Shor 's user avatar
4 votes

On the plausability of quantum RAM

To answer your question, a QRAM is a self-consistent and interesting model of quantum computation. It appears to be more powerful (up to a polynomial factor) than the usual circuit model of quantum ...
Peter Shor 's user avatar
4 votes
Accepted

What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?

Regarding the title of the question: What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems? and in particular the statement in the body: There is an ever [...
Mark S's user avatar
  • 1,125
4 votes
Accepted

Does Rush-Hour (or Klotski) admit a search-to-decision reduction?

Yes! As long as we can give the oracle a limit on the number of steps in a path, I think we can do it this way: Set $k\leftarrow n^3$ and set $B\leftarrow B_0$, where $B_0$ is the initial ...
wobtax's user avatar
  • 96
3 votes
Accepted

Comparing Shor's and Regev's Quantum Factoring algorithm

First some background (that does not fit the comments section) since you asked for pointers: The continued fractions-based post-processing algorithm in Shor's order-finding algorithm [Shor94] [Shor97]...
Martin Ekerå's user avatar
1 vote
Accepted

Could an *implicitly* defined graph be a member of a *strongly-explicit* family of expanders?

Yes! But I can see why it is confusing. A strongly explicit graph family $\{G_n = (V_n,E_n)\}$ (parameterized e.g. by number of vertices $n$) is described by an efficient ($\mathrm{polylog}(n)$ time) ...
smapers's user avatar
  • 849
1 vote
Accepted

Impact HHL caveat relaxation on quantum advantage

Your link 404's, but certainly HHL, like most quantum (and classical!) algorithms include a number of caveats for their applicability. The runtime of HHL depends on a number of factors in addition to ...
Mark S's user avatar
  • 1,125

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