# Tag Info

## Hot answers tagged quantum-computing

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

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 ... 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 ... 18 Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation - Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev 18 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 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 ... 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 I'd say we have no good reason to think BQP is in P/poly. We do have reasons to think that BQP is not in P/poly, but they're more-or-less identical to our reasons to think that BQP≠BPP. E.g., if BQP⊂P/poly then Factoring is in P/poly, which is enough to break lots of cryptography according to standard security definitions. Also, as you correctly ... 14 There are some relatively recent papers by Emanuele Viola et al., which deal with the complexity of sampling distributions. They focus on restricted model of computations, like bounded depth decision trees or bounded depth circuits. Unfortunately they don't discuss reversible gates. On the contrary there is often loss in the output length. Nevertheless ... 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 ... 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 ... 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 Short answer. For quantum circuits, there is at least one non-limitation result: arbitrary bounded-depth quantum circuits are unlikely to be simulatable with small multiplicative error in the probability of the outcome, even for polynomial-depth classical circuits. This, of course, does not tell you what resctrictions$\mathsf{QNC^0}$circuits will ... 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

I'll take a shot at your first question: Are there examples of natural function families that quantum computers can learn faster than classical computers given cryptographic assumptions? Well, it depends on the exact model and the resource being minimized. One option is to compare the sample complexity (for distribution-independent PAC learning) of the ...

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.

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