5
$\begingroup$

For a natural number $k$ (0 is a natural number), let $T_k$ be the collection of all languages that can be efficiently decided by quantum circuits consisting of Clifford gates and at most $k$ $T$-gates (that is, we modify the definition of $BQP$ so all circuits consist only of Clifford gates and at most $k$ $T$-gates).

Is it possible to show that $T_k \subsetneq T_{k+1}$ for each $k$? In particular, can we show that $T_0 \subsetneq T_1$?

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ each post should contain a single, laser-focused question. This makes it easier to get answers and makes the posts easier to search and retrieve afterward. You can open different posts to ask different questions. Feel free to edit this post to focus it on a single point. $\endgroup$
    – glS ♦
    Sep 3, 2021 at 12:41
  • $\begingroup$ +1; Gottesman-Knill states that the subspace reachable with only Clifford gates is discrete. My intuition is that Clifford + a bounded number of $T$-gate is still discrete., but likely bigger than the one below it. You might run in to uniformity issues in formalizing your question - e.g. for $T_1$ do you only allow one $T$ gate, no matter how many qubits $n$ you have? $\endgroup$
    – Mark Spinelli
    Sep 3, 2021 at 17:54
  • $\begingroup$ @MarkS This is my intuition as well. I think that the number of $T$-gates in the question should be independent of the number of qubits (so $T_1$ only allows 1 $T$-gate), otherwise the number won't really be bounded. But if you have a different interpretation of the problem, I'd be happy to consider it as well. $\endgroup$
    – Haim
    Sep 3, 2021 at 17:58
  • 2
    $\begingroup$ @glS I really view these 3 questions as subquestions of the one mentioned in the title, so it makes more sense to put them in the same place rather than having three separate questions where each refers to the others and where the introduction and definitions are more or less repeated. Having said that, I'll consider a different format for future questions. $\endgroup$
    – Haim
    Sep 3, 2021 at 18:03
  • 1
    $\begingroup$ I've commented out questions 2 and 3. I appreciate that they are "subquestions" of the question in the title, but that's just not the way it works on this platform. Answers get voted on, and things get messy if you ask more than one subquestion in the same post. You can recover your subquestions 2-3 by looking at the edit history. @AdamZalcmann hopefully you can save your draft for the answers to 2-3 somewhere, and hopefullly Haim asks those questions separately! $\endgroup$
    – user1271772
    Sep 3, 2021 at 19:27

1 Answer 1

Reset to default
2
$\begingroup$

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 exponential in $T$).

You might have a hierarchy within $P$, but at any level of your hierarchy, you're not dependent on $n$.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.