Questions tagged [complexity-theory]
For questions regarding complexity analysis of quantum algorithms and comparisons with complexities of classical algorithms.
363 questions
0
votes
0
answers
9
views
Block Encoding Matrices with Single-Entry Columns
I am working with an $N \times N$ matrix $A$ whose columns are computational basis vectors:
$$
A = [e_{i_0}, e_{i_1}, \dots, e_{i_{N-1}} ] = \sum_{j=0}^{N-1} |i_j\rangle \langle j|,
$$
where each $i_j ...
- 315
1
vote
1
answer
81
views
Why is the fastest quantum time complexity of unstructured search O(sqrt(n))?
Recently, I have watched video on 3Blue1Brown about Grover's algorithm. He give an example that:
To find a secret number in the range from 0 to n−1, you can query a
hidden function that returns “true”...
- 13
0
votes
0
answers
51
views
Using restarts to prove QMA in PP
I am going through Ryan O'Donnell's quantum computing class homeworks, and on problem 6 of this assignment you are asked to prove $QMA$ in $PP$ using the fact that $RestartingPP = PP$, where $...
0
votes
0
answers
52
views
Understanding theorem 6 of postBQP=PP paper
In this paper, $\mathsf{BQP}_p$ is defined to be similar to $\mathsf{BQP}$ in all aspects except that the Born's measurement rule is changed. For a normalised state
$$|{\psi}\rangle =\sum_x \alpha_x |...
- 953
2
votes
1
answer
141
views
What is the precise complexity of finding the ground state of 1-Local Hamiltonian?
I am studying the Local Hamiltonian problem.
Now the complexity of 1-local Hamiltonian is withing P Time. However what is it complexity class classification precisely?
I am most interested in if it in ...
0
votes
1
answer
60
views
What is the complexity class of solving the Poisson Equation?
I am interested in this published paper by Cao et al. here - see also arXiv version here.
This paper purports that Quantum Computers can solve the Poisson Equation on a Grid.
However this paper by ...
2
votes
2
answers
218
views
Can someone explain the Quantum Merlin Arthur complexity class in simple words?
I'm not big on computational complexity theory; I only know a little about classes like P and NP. I would appreciate it if someone could shed light on the idea behind the Quantum Merlin Arthur ...
- 33
2
votes
0
answers
48
views
What is the complexity of Local Quantum Search?
I am interested in this paper: https://arxiv.org/abs/2403.03237.
In my reading of this paper, it says that Local Quantum Search solves average case k-SAT in polynomial time.
I believe that my reading ...
7
votes
1
answer
121
views
How does Nielsens complexity relate to gate complexity numerically
Nielsens complexity describes the distance of a unitary operator to the identity operator in the manifold of unitaries.
It is know to be a lower bounds to the gate complexity, as shown here.
How does ...
- 63
2
votes
0
answers
42
views
How can the adversary method for proving lower bounds be used for search problems, instead of decision ones?
In this paper (page 2), the authors derive a lower bound in the quantum query complexity model for a Boolean function (i.e. decision problem) $f$ using the following formula: $$\mathrm{ADV}(f) = {\...
- 121
0
votes
0
answers
87
views
Understanding the "pairing function" in the definition of QCMA
By definition, a language $L$ is in $QCMA$ if and only if there exists a polynomial $p$ and a uniform and polynomial size quantum circuit family $Q$ such that for all $x$, if $x \in L$, then there ...
- 601
4
votes
1
answer
296
views
Complexity of finding a fixed-point of a unitary / eigenstate with eigenvalue 1?
Recently, while working on a problem I've been trying to solve I came across a formulation that requires me to find $|\phi\rangle$, such that
$$U|\phi\rangle = |\phi\rangle$$
Of course this ...
- 366
2
votes
1
answer
224
views
Complexity of checking if a circuit is deterministic or not?
Suppose I am given a list of gates for some circuit. I start with some fixed state, say $\vert 000..\rangle$, and measure the output in the computational basis. I want to know if the circuit is ...
- 3,385
0
votes
0
answers
85
views
Relationship between a language and promise problem class
What is the relationship between $\textbf{precise-promiseQCMA}$ and $\textbf{precise-QCMA}$?
Cross-posted on Theoretical Computer Science Stack Exchange.
I was recently reading about precise ...
- 31
1
vote
2
answers
168
views
Is there a sign-problem when the wavefunction itself has positive and negative values, or is it only when the Hamiltonian has such entries?
Consider the following two problems:
Let $A$ be an $s$-sparse $2^n\times 2^n$ Hermitian matrix with entries $A_{jk}$ in $\{0,1,-1\}$ both along the main diagonal and off the diagonal. Let $|\psi\...
- 16.3k