New answers tagged complexity-theory
0
First, you need to get familiar with the notion of classical complexity and big-O notation. For this, I recommend:
MIT 16.070 Big O notation lecture notes
Computational Complexity: A Modern Approach
The Complexity Zoo and links in the See Also section.
After getting a good grasp about classical complexity theory, you can start diving into quantum ...
1
The query complexity is usually spoken about with respect to an oracle or black-box function. It is the numbers of times you make use of that oracle in your algorithm (each time you use it, you are said to be "querying it", hence the terminology "query complexity"). It might be that you use the oracle many times in a single run of the ...
1
Before talking about upper bounds for $\mathsf{QMA(k)}$, let us first concentrate on upper bounds for $\mathsf{QMA(k)}$.
Recall that the maximum acceptance probability of a $\mathsf{QMA(k)}$ verifier $V_x$ is $\max_{|\psi\rangle} \||1\rangle\langle 1|_{out} V_x |\psi\rangle |\bar{0}\rangle\|_2^2$ where $|\bar{0}\rangle$ are ancillary qubits. It is a ...
2
I think your hierarchy collapses, or at least would never get beyond $P$, following the top-line results of Bravyi and Gosset.
Bravyi and Gosset's paper gives an algorithm to classically simulate a quantum circuit on $n$ qubits comprising $O(\mathrm{poly\:}n)$ Clifford gates and a constant number of $T$ gates - that is, polynomial in $n$ (although ...
1
Disclaimer
This answer to my own question does not completely answer the question but does cover some it the relevant points and hopefully can help anyone still considering answering or is interested in the problem I posed. Any answer from now on will be accepted and gain the bounty if it explains the remaining discrepancy in my complexity and explains why ...
Top 50 recent answers are included