Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
41 votes

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 ...
Robin Kothari's user avatar
31 votes
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 ...
wwjohnsmith1's user avatar
30 votes
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: ...
Craig Gidney's user avatar
  • 1,518
18 votes
Accepted

What does a tangible Quantum-Gate look like?

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, ...
Peter Shor 's user avatar
18 votes
Accepted

Is relation between BQP and QMA resolved?

I haven't looked at the paper carefully, but one thing I noticed is that their proof that BQP $\subsetneqq$ QMA works by their claiming that "bit commitment $\not \in$ BQP" but "bit ...
Peter Shor 's user avatar
13 votes

Is the 2016 implementation of Shor's algorithm really scalable?

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 ...
Peter Shor 's user avatar
13 votes

Is the wording of Google's QC Supremacy valid?

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). ...
domotorp's user avatar
  • 14k
13 votes
Accepted

How do separations of query complexities imply complexity class separations relative to oracles?

Let $\mathscr{F}$ be the collection of all functions $F:\{0,1\}^*\rightarrow\{0,1\}^*$, such that for every $n$, the restriction $F_n:=F|_{\{0,1\}^n}$ (restriction of $F$ on $\{0,1\}^n$) satisfies the ...
Wei Zhan's user avatar
  • 903
11 votes

What would a very simple quantum program look like?

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 ...
Robert Lisiecki's user avatar
11 votes
Accepted

Is there a survey of the field of quantum automata?

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 ...
Abuzer Yakaryilmaz's user avatar
11 votes

PPAD and Quantum

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. ...
Aviad Rubinstein's user avatar
10 votes

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 ...
Lieuwe Vinkhuijzen's user avatar
9 votes

List of quantum-inspired algorithms

There's also a recent work on low-rank semidefinite programming that, though not based directly on a quantum algorithm, still uses the same quantum-inspired techniques.
Ewin's user avatar
  • 91
9 votes
Accepted

String theory based computations

No, as far as I know, there are no models that use string theory. Given that quantum field theories seem to be simulatable in polynomial time by a quantum computer (Jordan, Lee, and Preskill, 2012), ...
Peter Shor 's user avatar
9 votes

Why exactly are complexity theorists interested in closed timelike curves?

Sorry for the very "big picture" answer from a non-quantum-theorist, but this contrast might help: you could describe algorithms as the study of how to solve computational problems, whereas complexity ...
usul's user avatar
  • 7,615
9 votes
Accepted

Why exactly are complexity theorists interested in closed timelike curves?

I think the big question here is "What does the complexity/power of algorithms look like in our universe?" If we ignore relativity and QM, then plain vanilla Turing machines are a decent model. But ...
Joshua Grochow's user avatar
9 votes

PPAD and Quantum

I will attempt to elaborate a bit on why CHKPRR shows that $\mathsf{PPAD}$ is plausibly hard for quantum computers. At a high level, CHKPRR builds a distribution over end-of-line instances where ...
Geoffroy Couteau's user avatar
8 votes
Accepted

theorems for universal set of quantum gates for SU(d)

I'm not aware of any proof that the Clifford group + any non-Clifford element gives a universal set of quantum gates. The closest related result that I know is that the Clifford group + any non-...
Adam Bouland's user avatar
8 votes
Accepted

Fast classical simulation of quantum algorithms

Your question was inspired by the recent quantum-inspired classical advance in recommendation algorithm. Note that it is not the firs time such a thing happens. In 2015, similar developments happened ...
Frédéric Grosshans's user avatar
8 votes
Accepted

Is there any quantum analog of the VP vs. VNP problem?

This is not quite an answer, but some observations that are too long for a comment. I've thought about this question before, but not being an expert in quantum I was never really able to resolve it. ...
Joshua Grochow's user avatar
8 votes
Accepted

Qubit gates in google supremacy

Based on a fairly cursory inspection of their paper, IBM is clearly aware of the spatial locality. They seem to in fact have taken spatial locality into account when designing their simulation. They ...
Peter Shor 's user avatar
8 votes
Accepted

Quantum Money where not even the Bank can counterfeit

There are proposals for quantum money where it appears that not even the bank can produce two copies of a quantum money state with the same serial number. See Farhi et al's paper Quantum Money from ...
Peter Shor 's user avatar
8 votes
Accepted

A contradiction in the realm of quantum digital and analog computation

Blum-Shub-Smale machines manage to solve NP-complete problems by using an exponential number of the digits of precision. Nothing that you can do in a physics experiment uses more than thirty digits of ...
Peter Shor 's user avatar
7 votes
Accepted

Is it possible to encrypt quantum states under reasonable assumptions?

One can encrypt an n-qubit state using a 2n-bit classical secret key. The idea is to use the key to select a random Pauli operator, and apply that operator to the secret as an encryption. (The inverse ...
Adam Smith's user avatar
7 votes

States and Probability distributions that the 5-qubits IBM computer can produce

I just ran the first state you suggest (i.e. the GHZ state with negative phase in the Hadamard basis). Basically what I did was to write a circuit which creates that state, apply one of 5 stabilizer ...
Joe Fitzsimons's user avatar
7 votes
Accepted

Numerical accuracy of superpositions in quantum computers

It appears that my question about "numerical accuracy" / error correction for qubits is nicely answered in the bible of quantum computation, M.A. Nielsen and I.L. Chuang, "Quantum Computation and ...
Heinrich Apfelmus's user avatar
7 votes
Accepted

Complexity of finding automorphism group of code

By taking direct sum of codes (given their two generator matrices $G_1, G_2$, consider the block matrix $G_1 \oplus G_2 = \begin{bmatrix} G_1 & 0 \\ 0 & G_2 \end{bmatrix}$), finding the ...
Joshua Grochow's user avatar
7 votes
Accepted

Are all computational models of quantum computing equivalent?

Now you've clarified your question, I can answer it. Assuming that the seminar was talking about universal quantum computational models (and there are universal computational models for all of these ...
Peter Shor 's user avatar
7 votes

Richard Feynman says that all quantum procedures are able to be simulated by quantum computation

Since we don't know the ultimate physical laws of the universe, and we would need to know them (or at least know much more about them than we do now) to prove Feynman's conjecture, his conjecture is ...
Peter Shor 's user avatar
6 votes
Accepted

Why is it impossible to work with polylog length encoding schemes for quantum circuits?

Clearly you can work with abstract compressed representations of circuits. You can reason about them and manipulate them and turn them into concrete lists of gates. We do it all the time. But in ...
Craig Gidney's user avatar
  • 1,518

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