150 votes
Accepted

Was the reduction in Shor's algorithm originally discovered by Shor?

I have to admit (surprising as it sounds) that I don't know really the answer. I either discovered or rediscovered this reduction myself. I discovered the discrete log algorithm first, and the ...
54 votes

Was the reduction in Shor's algorithm originally discovered by Shor?

The random reduction from factorization to order-finding (mod N) was very well known to people working in number theory algorithms in the late 1970's and early 1980's. Indeed, it appears in a paper ...
39 votes

Do any quantum algorithms improve on classical SAT?

Indeed, as wwjohnsmith1 said, you can get a square root speed-up over Schöning's algorithm for 3-SAT, but also more generally for Schöning's algorithm for k-SAT. In fact, many randomized algorithms ...
30 votes
Accepted

If P = NP were true, would quantum computers be useful?

The paper "BQP and the Polynomial Hierarchy" by Scott Aaronson directly addresses your question. If P=NP, then PH would collapse. If furthermore BQP were in PH, then no quantum speed-up would be ...
30 votes
Accepted

Do any quantum algorithms improve on classical SAT?

I think one can obtain a non-trivial upper bound from quantum computing by speeding up the randomized algorithms of Schöning for 3-SAT. The algorithm of Schöning runs in time $(4/3)^n$ and ...
27 votes
Accepted

Oracle Construction for Grover's Algorithm

The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to. For example, suppose you have a 3-sat problem: ...
  • 1,468
24 votes
Accepted

Factoring as a decision problem

Here the goal is to construct a decision problem D so that (a) if you can factor you can solve the decision problem in polynomial time and (b) if you can solve the decision problem you can factor in ...
23 votes
Accepted

Problems in BQP but conjectured to be outside P

To have a list of such problems, you can look at the list of superpolynomial speed improvement at the quantum algorithm zoo (QAZ). The list below is based on this (see QAZ for precise definitions and ...
22 votes
Accepted

The randomized query complexity of the conjoined trees problem

I think I have a deterministic algorithm that finds the exit in $O(n2^{n/2})$ oracle calls. First, find the labels for all the vertices of distance $n/2$ from the entrance. This takes $O(2^{n/2})$ ...
  • 236
19 votes
Accepted

If BQP contains NP, does this mean that P=NP?

No, $\mathrm{NP}\subseteq\mathrm{BQP}$ is not known to imply $\mathrm P=\mathrm{NP}$. Even the stronger assumption $\mathrm{NP}\subseteq\mathrm{BPP}$ is not known to yield a deeper collapse than $\...
17 votes
Accepted

What does a tangible Quantum-Gate look like?

You seem to have the idea that a quantum gate is a physical thing rather than just a conceptual thing. It doesn't necessarily work that way. While CMOS gates are usually actual physical devices, ...
16 votes

Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?

P and BQP are decision-problem classes, i.e. the correct output is always a deterministic functions of the inputs. The only question is whether randomness helps "along the way" to speed up computing ...
  • 7,090
13 votes
Accepted

Quantum algorithms for QED computations related to the fine structure constants

The general belief seems to be that the expansion in $\alpha$ is an asymptotic series but not a convergent series. The handwaving estimate is that in $\sum_k c_k \alpha^k$, the scaling for the ...
  • 558
13 votes

Is the wording of Google's QC Supremacy valid?

You should read the new post by Aaronson, but until then the short answers: No. If you can realize it in a real world machine, then it would (if no one finds a fast, classical algorithm until then). ...
  • 13.6k
12 votes

Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?

The questions touches on some very interesting issues regarding quantum computation (and randomness). BQP is the class of decision problems that can be solved efficiently (in polynomial time) but it ...
  • 6,083
12 votes

Is the 2016 implementation of Shor's algorithm really scalable?

The main thrust of Cao and Luo's argument is that in the variant of the algorithm that was implemented, the first register—that eventually contains the output—contains only 1 bit. And if you only get ...
11 votes

What would a very simple quantum program look like?

It looks like this: You too can have access to a real quantum processor. Go here and sign up: http://www.research.ibm.com/quantum/ It also includes a simulator so you can test without using actual ...
11 votes
Accepted

Runtime of Grover's algorithm

The question is usually taken to be moot, for the following reason. Grover's algorithm is a combinatorial search algorithm to find a solution to an arbitrary predicate. While, yes, $\Theta(\log N)$ ...
11 votes

Are there any cases where quantum has given insight for classical algorithms?

There is at least one example that I can remember, but there are probably more that I am not aware of. Recently, Maarten Van den Nest and Wolfgang Dürr found a new classical algorithm (arXiv:1304....
11 votes
Accepted

Why is shifting bits different from shifting qubits?

It's complicated, and depends on whether you approach quantum computing as a technology or a model of computation; and whether you are interested in universal quantum computation, or a special ...
11 votes

Is the Presburger arithmetic decision problem known to be outside of BQP or BPP?

Let $~{\mathrm{PRESARITH}}$ denote the decision problem of the truth of statements in Presburger Arithmetic. As you note, [Fischer+Rabin 1974] (PS manuscript) show that the nondeterministic time ...
11 votes
Accepted

Is there a survey of the field of quantum automata?

You can check the recent survey by Ambainis and Yakaryilmaz: Automata and Quantum Computing. It is comprehensive and points the essential literature with some open questions. Moreover, here is a list ...
11 votes

PPAD and Quantum

Two answers that I learnt while writing a blog post about this question No: In black-box variants, quantum query/communication complexity offer the Grover quadratic speedup, but not more than that. ...
10 votes

Are there any cases where quantum has given insight for classical algorithms?

Quantum Proofs for Classical Theorems by Andrew Drucker and Ronald de Wolf is a very nice survey on this topic. One of the first classical results obtained by thinking about the problem quantumly was ...
10 votes

Is it conceivable at all that the standard model of physics can outperform a quantum computer in any sense?

If quantum computers can simulate in polynomial time the Standard Model, which is a quite complicated quantum field theory, then probably the Standard Model does not provide any extra computational ...
10 votes
Accepted

Consequences of $NP\subseteq P/poly$ to $BQP$

I'm not aware of any direct consequence of $NP\subset P/poly$ for $BQP$. Of course it might lessen the interest in quantum computing, since it would mean that we could do something far more ...
10 votes

Quantum polynomial hierarchy vs counting hierarchy

I was quite surprised as well to not find this hierarchy in the literature, so I wrote my graduate thesis about it. It will be available online soon, at which point I will update this answer with a ...
9 votes

Is any QMA-intermediate problem known?

An example would be the computation of ground state energy of the Ising model with transverse magnetic fields, as described by [Cubitt+Montenaro-2013]. From the abstract: In this work we ...
9 votes
Accepted

Applications of HHL's algorithm for solving linear equations

If by "classically using the solutions of the linear equation" you mean "accessing the information in the exactly same way a classical computer does" or, in other words, "obtaining the classical ...
9 votes

Factoring as a decision problem

Yes, there is a paper by John Watrous, which formally addresses the concerns raised on Lipton's blog (reported in user2917198's comment). Here is the reference: J. Watrous. An introduction to quantum ...

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