patternMinor
Are there any useful deterministic quantum algorithms for decision problems?
Viewed 0 times
areanyproblemsalgorithmsdecisiondeterministicusefulfortherequantum
Problem
The vast majority of known interesting quantum algorithms are probabilistic. The only deterministic quantum algorithms that I know of (which aren't trivially equivalent to a classical algorithm) are (a) Deutsch's algorithm, in which the quantum speedup is pretty trivial, (b) the Deutsch-Josza algorithm, which solves a promise problem rather than a decision problem, and (c) this algorithm (which I found by Googling): http://arxiv.org/abs/1108.5848, which also doesn't solve a decision problem. Are there other known examples of "interesting"/"useful" deterministic quantum algorithms, especially for decision problems?
I know that this question isn't particularly well-formulated, because which algorithms you can use depends on which set of quantum gates you have available. Are there any interesting algorithms that use only a "realistic" set of quantum gates? (Say, only the quantum gates that can be currently purchased on Amazon for under $10 :-) .)
I know that this question isn't particularly well-formulated, because which algorithms you can use depends on which set of quantum gates you have available. Are there any interesting algorithms that use only a "realistic" set of quantum gates? (Say, only the quantum gates that can be currently purchased on Amazon for under $10 :-) .)
Solution
There are some query complexity results that mention exact quantum algorithms. See this blog post about the paper "Separations in Query Complexity Based on Pointer Functions":
a total boolean function $g$ on $n$ variables that has [...] exact quantum query complexity [...] $Q_E(g) = \tilde O(\sqrt n)$.
More generally, the complexity class you're looking for is called EQP: Exact Quantum Polynomial-Time.
EQP is not a very "nice" complexity class, especially compared to BQP. There's two big reasons for that:
-
Theoretical-side, there's no universal set of gates. EQP circuits may require a gate with irrational coefficients such as $\begin{bmatrix} \cos(10^\circ) & -\sin(10^\circ)\\ \sin(10^\circ) & \cos(10^\circ)\end{bmatrix}$, and approximations via other gates aren't allowed. So you end up with a bunch of different $\text{EQP}_{my\_favorite\_gate\_set}$s instead of a nice unified one.
-
Practical-side, there's no possibility of error correction. EQP lives in a world without errors, because otherwise it wouldn't be exact. Error correction is expected to be a necessity in practice, so if you care about actual implementation then you don't care much about EQP.
a total boolean function $g$ on $n$ variables that has [...] exact quantum query complexity [...] $Q_E(g) = \tilde O(\sqrt n)$.
More generally, the complexity class you're looking for is called EQP: Exact Quantum Polynomial-Time.
EQP is not a very "nice" complexity class, especially compared to BQP. There's two big reasons for that:
-
Theoretical-side, there's no universal set of gates. EQP circuits may require a gate with irrational coefficients such as $\begin{bmatrix} \cos(10^\circ) & -\sin(10^\circ)\\ \sin(10^\circ) & \cos(10^\circ)\end{bmatrix}$, and approximations via other gates aren't allowed. So you end up with a bunch of different $\text{EQP}_{my\_favorite\_gate\_set}$s instead of a nice unified one.
-
Practical-side, there's no possibility of error correction. EQP lives in a world without errors, because otherwise it wouldn't be exact. Error correction is expected to be a necessity in practice, so if you care about actual implementation then you don't care much about EQP.
Context
StackExchange Computer Science Q#57360, answer score: 4
Revisions (0)
No revisions yet.