5

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$?

user1271772 No more free time
  • 13,847
  • 2
  • 25
  • 71
Haim
  • 257
  • 1
  • 7
  • 1
    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. – glS Sep 03 '21 at 12:41
  • +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? – Mark Spinelli Sep 03 '21 at 17:54
  • @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. – Haim Sep 03 '21 at 17:58
  • 2
    @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. – Haim Sep 03 '21 at 18:03
  • Well, the total number of gates in Clifford +unbounded $T$ still has to be polynomially bounded in the number of qubits $n$ to be in BQP. You seem to be asking about Clifford + $O(1)$ $T$ gates. It might be interesting to ask about Clifford + $O(\log n)$ $T$ gates. – Mark Spinelli Sep 03 '21 at 18:14
  • I agree with @gIS. I started writing an answer for 2 and 3, but discarded it since I don't know the answer to 1. Even though these questions share a definition (that is short enough to just copy paste into each question), the character of each of the three questions is quite different. Generally speaking, it's a matter of simple math: chances that a single person has the time and knowledge to answer $N$ questions is simply not as high as the chance that $M$ people have the time and knowledge to answer $N$ questions one by one. – Adam Zalcman Sep 03 '21 at 18:33
  • 1
    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! – user1271772 No more free time Sep 03 '21 at 19:27
  • Also, does this question and answer help? There's a paper by Bravyi and Gosset, that shows that simulation is polynomial in Clifford, but exponential in $T$. For $T$ constant and independent of $n$ as in your question, it's still polynomial. – Mark Spinelli Sep 03 '21 at 19:47
  • @MarkS Thanks! This answers Q2 completely and implies an answer to Q3 (namely any natural BQP-complete problem would do). So I guess there is no need to repost those two questions now. – Haim Sep 03 '21 at 20:02

1 Answers1

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

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

Mark Spinelli
  • 11,947
  • 2
  • 19
  • 65