The Stack Overflow podcast is back! Listen to an interview with our new CEO.
139

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


59

Caveat Emptor: the following is heavily biased on my own research and view on the field of QC. This does not constitute the general consensus of the field and might even contain some self-promotion. The problem of showing a 'hello world' of quantum computing is that we're basically still as far from quantum computers as Leibnitz or Babbage were from your ...


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


33

It seems like this interaction can be modeled in the following way: Alice prepares one of the states $|000\rangle$, $|101\rangle$,$(|0\rangle+|1\rangle)|10\rangle/\sqrt{2}$, $(|0\rangle-|1\rangle)|11\rangle/\sqrt{2}$, according to a certain probability distribution, and sends the first qubit to Bob. Bob performs an arbitrary quantum channel that sends his ...


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.


30

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


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


21

I assume that C's libquantum, Haskell's quantum monads or Perl's Quantum::Entanglement all represent quantum computations faithfully. You might look at their examples. In general, you describe a quantum algorithm as a classical algorithm that applies a series of linear operators to a super-position representing the state of your quantum system. Journal ...


21

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


19

The question of cloning the BB84 states was covered in the paper "Phase covariant quantum cloning" by Dagmar Bruß, Mirko Cinchetti, G. Mauro D'Ariano, and Chiara Macchiavello [Phys Rev. A, 62, 012302 (2000), Eq. 36]. They give an optimal cloner for these states (which is also an optimal cloner for any states $\alpha |0\rangle + \beta |1\rangle$ with $\alpha$,...


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


17

To complement what Joe wrote, and maybe explain this question a bit more (without answering it!): The computational complexity of simulating "realistic" quantum field theories has been considered an open problem for a long time. One of the main problems, as I understand it, is that (3+1)-dimensional QFTs aren't sufficiently well-defined mathematically for ...


17

Efficiently simulating quantum mechanics.


17

You're really asking two different questions and hoping that there is a single response which answers both: (1) What natural notions of quantum monotone circuits are there? (2) What would a lattice-based Razborov-style quantum result look like? It isn't obvious how to achieve both at the same time, so I'll describe what to me seems a reasonable notion of ...


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

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

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


15

There are many examples in quantum information and computation where quantities of interest are expressible as optimal values of semidefinite programs. Here are a few beyond those mentioned in the question: The optimal probability to correctly distinguish states chosen from a known ensemble is expressible as an SDP. (See arXiv:quant-ph/0205178 .) The ...


15

With respect to your third question, Aaronson and Arkhipov (A&A for brevity) use a construction of linear optical quantum computing very closely related to the KLM construction. In particular, they consider the case of $n$ identical non-interacting photons in a space of $\text{poly}(n) \ge m \ge n$ modes, starting in the initial state $$ \left|1_n\right&...


15

The highest threshold lower bound for for independent stochastic noise of which I am aware is $1.04 \times 10^{-3}$ by Aliferis, Gottesman and Preskill (quant-ph/0703264). They analyze Knill's teleportation-based scheme with postselection. If you are willing to consider independent depolarizing noise, then I know of two slightly higher lower bounds: $1.25\...


14

Why do you think simulating quantum physics means that you have to efficiently implement arbitrary quantum $n$-way interactions? If that's your requirement, quantum computers cannot do it efficiently. You can write down an $n$-way unitary gate which implements an arbitrary $n$-bit-input $n$-bit-output function. This would let us solve an arbitrary problem ...


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

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

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


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