# Tag Info

144

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.

25

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 ...

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 $\... 23 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 ... 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 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 ... 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 ... 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 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 ... 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 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 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 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 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 ...

11

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 complexity of $\mathrm{PRESARITH}$ is at least $2^{2^{\Omega(n)}}$. In particular, $\mathrm{PRESARITH} \notin \mathsf{NEXP}$. However, we have the containments \$...

11

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 is not clear that referring just to decision problems suffices to do justice to the power of quantum computing. If we let QSAMPLING describes the probability ...

11

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 of papers published on quantum automata until 2015.

11

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. As Ron points out, this extends to computational complexity under plausible assumptions. Maybe: Nash equilibrium is arguably the flagship problem of "Christos ...

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