I want to simulate a 40-45 Qubit circuit that applies Grover + QPE.

I've tried running a simulation on qiskit but can't really go past 18 qubits on my machine. As an alternative, I've been reading Bravyi's work using a technique called Low-Rank Stabilizer decomposition, but I am confused as to where to start or how to translate everything into workable code.

Could you recommend me any references which could help me understand Bravyi's work (or maybe some implemented code)?


1 Answer 1


I agree that the Bravyi et al. paper is not easy to understand and they should have made some reference implementation available.

Without going into details, I don't think it is likely to get an improvement. For Grover alone, you need to do $O(2^{n/2})$ steps and in each step, you basically do a rotation. This rotation is very unlikely to be Clifford, thus you apply $O(2^{n/2})$ non-Clifford gates. Any stabiliser-based simulation method eventually scales exponentially with the number of non-Clifford gates. Thus, this should explode very fast.

(Well, this should hold for any simulation method in this context).

So as long as you don't find a smart recompilation which reduces the "magic" in the circuit (which is probably highly non-trivial), I would say that there is not much to gain.

Perhaps, you could have a look at the very recent paper by Hakop Pashayan et al. There is also a QIP talk on Youtube from last week.

Their technique is quite unique and might get you somewhere. So far, I cannot really judge how far, because I don't understand it well enough. But, they provide an implementation of their algorithm on github (Ref. [35] in their paper).

  • $\begingroup$ Are you interested in sharing a link to the github repo within your answer? I think it would benefit well, for future reference etc. $\endgroup$
    – JSdJ
    Commented Feb 11, 2021 at 9:28
  • 1
    $\begingroup$ The repo is given in the paper, but I added it for convenience. I also added a link for the recorded QIP talk $\endgroup$ Commented Feb 11, 2021 at 10:12
  • $\begingroup$ Hey Heinrich, thanks for the feedback! I am applying Brassard's Q operator for amplitude amplification (arxiv.org/pdf/quant-ph/0005055.pdf) instead of directly grover's diffuser, and it amounts to two. n-qubit controlled Z rotations + 2 times QPE, theoretically i could decompose the n-controlled Z rotation into 2-qubit controlled z-rotations (with bigger theta rotations) + controlled-nots, wouldn't that be considered clifford? $\endgroup$ Commented Feb 11, 2021 at 14:50
  • $\begingroup$ @CésarLeonardoClementeLópez Well, the only controlled Z-rotation, which is Clifford, is CZ itself, so these gates are non-Clifford. Multiply-controlled Z rotations are never Clifford. It might be possible to work out some details for this case, but I think the fundamental problem persists. $\endgroup$ Commented Feb 11, 2021 at 16:32

Your Answer

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

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