Unanswered Questions
76 questions with no upvoted or accepted answers
5
votes
0
answers
129
views
Why is there no $N$ in the time complexity of the QLSP algorithm by Childs et al.?
The paper Quantum linear systems algorithms: a primer by Dervovic et al has this table on page 3:
I'm not sure why there's no $N$ in the time complexity of the algorithm by Childs et al. i.e. $\...
- 17.7k
4
votes
0
answers
47
views
Alternative algorithm for quantum phase estimation problem
The Quantum Phase estimation problem is stated below:
Input: Given $U$ as a unitary operator acting on an m-qubit register. If $| \psi \rangle$ is an eigenvector of $U$, then U$| \psi\rangle$ = $e^{ ...
- 14.6k
4
votes
0
answers
46
views
Can we have a constant-overhead threshold theorem?
The threshold theorem states that any abstract circuit in BQP can be computed by another polynomial-depth circuit that succeeds in the presence of noise. The original construction from 1996 requires ...
- 430
4
votes
0
answers
37
views
Is there a general framework that allows us to compare probabilistic and deterministic algorithms fairly?
Many popular QC algorithms are probabilistic in nature, like Grover's, Shor's, QAOA ..etc
For some of these we have formulas that give probabilities of success (like for Grover's and Shor's), and for ...
- 271
4
votes
0
answers
104
views
Relation between geometric and discrete circuit complexity
Geometric complexity of a unitary, as introduced for example here https://arxiv.org/abs/quant-ph/0502070, measures the length of a geodesic connecting the identity matrix and a given unitary in the ...
- 1,655
4
votes
0
answers
125
views
Is the exponential speedup and output $\langle x|M|x\rangle$ in contradiction in HHL algorithm?
Isn't the exponential speedup and the output $\langle x|M|x\rangle$ in contradiction in HHL algorithm? How can we print the solution vector $|x\rangle$ without losing the exponential speedup?
glS♦
- 25.9k
4
votes
0
answers
71
views
Could quantum computers answer the question of whether QCD predicts quark gluon confinement?
As I understand it, it is not known whether or not QCD actually predicts quark gluon confinement.
As I understand it answering questions in quantum field theories is generally harder in terms of ...
- 153
4
votes
0
answers
69
views
Feynman method and polynomial time algorithm for XQUATH
Consider the Feynman algorithm for simulating quantum circuits, as given here.
Consider the XQUATH conjecture for random quantum circuits from here, given by
(XQUATH, or Linear Cross-Entropy Quantum ...
- 1,373
4
votes
0
answers
65
views
Query complexity on Quantum Pattern Matching of Mateus Algorithm
I am trying to understand the complexity of the Mateus and Omar algorithm for quantum pattern matching, it is clear to me from the pseudocode that the query complexity is $O(\sqrt{N})$, apart from the ...
- 2,915
4
votes
0
answers
78
views
What is the computational complexity of approximate quantum adders, in terms of big O notation?
I have recently found papers on approximate quantum adders. However, the papers do not seem to mention the computational complexities of their algorithms. What are their complexities, in terms of big ...
- 1
4
votes
0
answers
134
views
How close is the history state to the ground state in the Kitaev clock construction?
Consider a standard circuit to Hamiltonian reduction in QMA. For example, refer here (Vazirani's lecture notes) or page 235 of here (survey by Gharibian et al).
The history state of the Kitaev clock ...
- 1,373
4
votes
0
answers
65
views
Bound on quantum speedups under various models of complexity
What are the bounds on quantum speedups under the various models of complexity? How big or small can they be?
Under the query model, my understanding is that the lower bound is $\Omega(\sqrt{N})$ as ...
- 23.2k
4
votes
0
answers
227
views
What is the query complexity of the QUBO algorithm?
What is the complexity of the quantum unconstrained binary optimization (QUBO) algorithm in the number of queries to the quantum processor?
To clarify, I'm asking about the complexity on quantum ...
glS♦
- 25.9k
4
votes
0
answers
464
views
What is known about the quantum version of Schoening's algorithm for 3SAT?
Schoening's algorithm for 3SAT can be converted to a quantum algorithm. The classical circuit representing a 3SAT expression in CNF form can be converted to a quantum version involving reversible ...
4
votes
0
answers
81
views
Is either the adiabatic or the diabatic version of quantum annealing known to be theoretically more powerful than the other?
Quantum annealing can be considered either in the perfectly adiabatic "slow" limit (in which case it's usually referred as "adiabatic quantum computing" (AQC) instead of "...
- 2,851