143

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 factoring algorithm second, so I knew from discrete log that periodicity was useful. I knew that factoring was equivalent to finding two unequal numbers with equal ...


55

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 of Heather Woll, Reductions among number theoretic problems, Information and Computation 72 (1987) 167-179, and Eric Bach and I knew it before then. I am ...


34

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 for k-SAT can be implemented quadratically faster on a quantum computer. The reason for this general phenomenon is the following. Many randomized algorithms for ...


30

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 possible in that case. On the other hand, Aaronson gives evidence for a problem with quantum speedup outside PH, thus such a speed-up would survive a collapse of PH.


24

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 using standard amplitude amplification techniques one can obtain a quantum algorithm that runs in time $(2/\sqrt{3})^n=1.15^n$ which is significantly faster than ...


24

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: (¬x1 ∨ ¬x3 ∨ ¬x4) ∧ (x2 ∨ x3 ∨ ¬x4) ∧ (x1 ∨ ¬x2 ∨ x4) ∧ (x1 ∨ x3 ∨ x4) ∧ (¬x1 ∨ x2 ∨ ¬x3) Or, in table form with each row being a 3-clause, x meaning "this variable false", o ...


23

This is a question that is a little bit difficult to unpack if you are not familiar with computational complexity. Like most of the field of computational complexity, the main results are widely believed but conjectural. The complexity classes typically associated with efficient classical computation are $\mathsf{P}$ (for deterministic algorithms) and $\...


22

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})$ queries. Then, start from the entrance and walk $n+1$ steps to get to a node $X$ of distance $n+1$ from the entrance. We will try to reach the exit from this node....


22

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 references. This is another way to say I don’t even pretend to understand many of the problems of this list!) Algebraic and Number Theoretic Problems If I’m ...


20

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 polynomial time. There are a number of ways to do this. To name just two: D: given n and k, does n have a divisor d satisfying 1 < d <= k? D: given n ...


19

Two quick clarifications: Adiabatic QC is typically "based on qubits" just as much as circuit-based QC is -- I don't know where you got the idea that it isn't! (Though one could also use qutrits or other building blocks, in either the circuit or the adiabatic models.) As Mateus pointed out, the justly-famous result of Aharonov et al. says that "adiabatic ...


19

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 $\mathrm{NP}=\mathrm{RP}$ and $\mathrm{PH}=\mathrm{ZPP^{RP}}=\mathrm{BPP}$; in particular, it is not even known to imply $\mathrm{NP}=\mathrm{coNP}$. (However, all ...


18

Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation - Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev


17

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, quantum gates may be just conceptual. Consider an ion trap. The ions represent qubits by using one electronic state as a $|0\rangle$ and another as a $|1 \rangle$...


16

I would like to add some more references to Scott's comment: Indeed, Clebsch-Gordan transforms (that you can think of as multi-register quantum Fourier transforms) are a useful tool in the design of quantum algorithms for non-Abelian hidden subgroup problems (HSPs). Clebsch-Gordan transforms were used by Greg Kuperberg and Oded Regev to solve the dihedral ...


16

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 this deterministic function (at the cost of sometimes being wrong), or does not. This is the key point: P=BQP says nothing about outputting random strings in ...


14

First of all, there is a formal definition of "quantum-NC", see QNC on the zoo. GCD is indeed a good candidate for a problem that could be shown to be in QNC, but it's not known to be in NC. However, finding a QNC algorithm for GCD is still an open problem. The feeling for which this is believed to be true comes from the fact that the Quantum Fourier ...


14

Actually, today's computers can generate truly random data on their own, and many in fact do. The random data is produced as a byproduct of the physics of the components, not as the product of a given algorithm, so it necessarily has to be implemented in hardware. But the hardware is readily available. The popular TPM chip, for example, typically has an ...


13

The problem isn't clearly in coQMA. If $U_1$ and $U_2$ are different, and you're given a state on which they act differently, it is not necessary that a polynomial-time quantum computer can check that the output states are different. In fact, it is easy to show that if these two quantum states are different, but exponentially close in trace norm, then no ...


13

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). You don't prove anything. It's a practical fact, like AI playing chess better than humans. If a chess genius is born, (s)he might win back the crown for ...


12

There is a simple algorithm for V3. I'll use the convention that there are $(2n)^3$ possible clauses, so $2^{8n^3}$ formulas. (This is just for simplicity - if you don't want all $8n^3$ clauses to be considered valid, it wouldn't affect the following argument.) Pick a random assignment from $\{0,1\}^n$. For each of the $7n^3$ possible clauses that are true ...


12

If you're asking whether a quantum computer can compute any function that a classical computer can compute without using many more elementary computational steps, then the answer is yes: a quantum computer can perform any reversible classical computation, and if you keep the input around, any classical computation can be made reversible at a cost of ...


12

I apologize; I was too glib when I wrote that. While I believe it's possible to prove an oracle separation between $BQP$ and $BPP^{BQNC}$ using current techniques, it hasn't been done (12 years after I first thought about the problem, then put it off!), and would certainly be worth a paper for whoever did it. Maybe your post will help motivate me to ...


12

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 coefficients is roughly $c_k \sim k!$. So, since $\alpha \simeq 1/137$ the terms will start to get bigger rather than smaller for $k$ larger than around 137. (I assume ...


12

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 1 bit of output from the algorithm, that's insufficient for factorization. (For one thing, although this isn't their argument, 1 bit clearly does not contain ...


11

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 hardware, or use credits (free) to run on actual hardware.


11

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)$ is the quantum gate complexity in each stage of the black-box algorithm, the predicate needs to be computed too. The quantum gate complexity of that is $\...


11

The essential difference between quantum computation and parallelism is for the most part the same as between randomized computation (e.g. using coin-flips, or some other form of random number generation) and parallelism. In randomized computation, depending on the outcome of the coin-flips, you explore one out of many possible computational possibilities. ...


11

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.2879) to approximate certain types of partition functions (of 3-body classical Ising models on two-dimensional lattices. Their algorithm is completely classical, ...


11

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 subclass of quantum operations. As a technology We're still working on how to implement a large-scale quantum computer. Part of the reason for this is that it is a ...


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