# Tag Info

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 ...
• 23.8k

### 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 ...
• 6,908

### 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 ...
• 13.4k
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 ...
• 5,406
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 ...
• 316
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
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 ...
• 6,908
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 ...
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
Accepted

• 13.4k

### 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 ...
• 1,754

### 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 ...
• 8,841
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 ...
• 1,365