40
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 ...
- 13.5k
30
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 ...
- 316
29
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:
...
- 1,498
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, ...
- 24.3k
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 ...
- 24.3k
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).
...
- 13.9k
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 ...
- 111
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 ...
- 3,707
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. ...
- 111
11
votes
Accepted
How do separations in 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 ...
- 723
10
votes
Accepted
Consequences of $NP\subseteq P/poly$ to $BQP$
I'm not aware of any direct consequence of $NP\subset P/poly$ for $BQP$. Of course it might lessen the interest in quantum computing, since it would mean that we could do something far more ...
- 13.6k
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 ...
- 1,934
9
votes
Consequences of $NP\subseteq P/poly$ to $BQP$
If $\mathsf{NP} \subseteq \mathsf{P/poly}$, then $\mathsf{PH}$ collapses to $\mathsf{\Sigma_2 P}$ (Karp-Lipton), and in fact to $\mathsf{S_2 P}$ (attributed to Sengupta by Cai, FOCS 2001), and even to ...
- 36.9k
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.
- 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), ...
- 24.3k
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 ...
- 7,595
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 ...
- 818
8
votes
Evidence that there is some problem in BQP distinct from BPP?
Scott Aaronson has been addressing this topic: http://arxiv.org/abs/0910.4698
Related hardness results:
Boson sampling: http://arxiv.org/abs/1011.3245
Commuting circuits: http://arxiv.org/abs/1005....
- 5,446
8
votes
Runtime of Grover's algorithm
Turns out that there is a way to implement Grover's algorithm with fewer than $O(\sqrt{N}\log N)$ gates! That's why you were not able to find a reference claiming that $\Omega(\sqrt{N}\log N)$ gates ...
- 13.5k
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-...
- 743
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. ...
- 36.9k
8
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 ...
- 36.9k
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 ...
- 24.3k
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 ...
- 24.3k
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 ...
- 24.3k
7
votes
Accepted
How powerful is exact "quantum" computing if you suspend unitarity?
Short answer. It turns out that suspending the requirement of unitary transformations, and requiring each operation to be invertible, gives rise to exact gap-definable classes. The specific classes in ...
- 8,821
7
votes
Geometric picture behind quantum expanders
[This answer was copied from my answer on the now-defunct theoreticalphysics stackexchange site.]
For classical expanders, the spectral definition can be expressed in terms of the second-smallest ...
- 1,030
7
votes
Accepted
Quantum Hardness of Approximating Lattice Problems
The answer to your question is the same as with many other such assumptions in cryptography: despite a lot of effort no one has found any substantially faster quantum algorithms for lattice problems. ...
- 4,788
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 ...
- 878
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 ...
- 13.6k
Only top scored, non community-wiki answers of a minimum length are eligible