Qrack extended stabilizer for CDR and other near-Clifford applications

[WrathfulSpatula]

Pre-Request Checklist

• [x] I checked to make sure that this feature has not already been requested.

Issue Description

I would like to help the Mitiq team consider whether and how it can benefit from Qrack/PyQrack extended stabilizer simulation.

Proposed Solution

Over at the PyQrack repository, I will be officially releasing a compiled binary for extended stabilizer simulation this weekend. This has been implemented as a combination of implementations of quantum binary decision trees (QBDT) (as I learned about from presentations by Jülich Supercomputing Centre at IEEE Quantum Week, last October) and a C++ port for Aaronson's stabilizer tableau (CHP) simulation method. By the QBDT method, we can think of a register of coherent qubits as a tree of nodes with two complex amplitude branches apiece, each pair normalized to 1.0, (and with 0-most permutation phase factored up to the top of the tree, in every sub-tree). Worst case is exponential complexity, but, if a pair of branches both point to the same sub-tree, they are combined, for best case linear overhead (in my implementation, though this might even be reduced to constant complexity in best case).

It's possible to attach another type of qubit simulation at the deepest level of this quantum binary decision tree. An exponential (in worst case) number of copies must be made of the heterogeneous simulation method, each copy with a complex amplitude, and these "attachments" are handled according to the same normalization rules as QBDT branch pair nodes.

Possible "attachments" to QBDT include stabilizer simulation, which together constitute a novel method of (universal) extended stabilizer simulation. Since SWAP gates are Clifford, they can cross the effective "Clifford-permeable domain wall" between QBDT representation qubits and stabilizer qubits. Further, if we want to act a universal gate on stabilizer qubits, if we SWAP stabilizer qubits with QBDT qubits (which is perfectly permissible, being a Clifford gate) then we can act universal gates after SWAP on universal QBDT qubits, then SWAP back to stabilizer qubits!

The limitation is numerical precision lost in this process. I can confirm that significant fidelity is lost in Haar-random circuit tests, this way, although this is not unexpected. However, near-Clifford simulation with a small number of non-Clifford/Pauli gates sees a lower reduction in fidelity.

I'd love it, if this (fast!) extended stabilizer simulation method could be useful to Mitiq, as for CDR!

Additional References

https://github.com/vm6502q/qrack/blob/main/include/qbdt.hpp (Qrack QBDT header) https://github.com/vm6502q/qrack/tree/main/src/qbdt (Qrack QBDT body implementations) https://github.com/vm6502q/qrack/blob/main/include/qstabilizer.hpp (Qrack stabilizer tableau header) https://github.com/vm6502q/qrack/blob/main/src/qstabilizer.cpp (Qrack stabilizer tableau body implementations)

https://arxiv.org/abs/1911.12691 (How to Efficiently Handle Complex Values? Implementing Decision Diagrams for Quantum Computing) https://www.scottaaronson.com/papers/chp6.pdf (Improved Simulation of Stabilizer Circuits)

[github-actions[bot]]

Hello @WrathfulSpatula, thank you for your interest in Mitiq! If this is a bug report, please provide screenshots and/or minimum viable code to reproduce your issue, so we can do our best to help get it fixed. If you have any questions in the meantime, you can also ask us on the Unitary Fund Discord.

[WrathfulSpatula]

Going into Monday, I'm still working on debugging and now finishing the implementation of the proposed method on the Qrack end. I have a fairly complete design, of implementing Qrack::QStabilizerHybrid as a QEngine type, interfacing with QBdt via QStabilizerHybrid, and treating QStabilizer like a special quasi-QEngine case only when conditions are symmetric enough.

It might take another week, though. So, there's no hurry on this issue ticket, but we can still discuss design and implementation at any point that's convenient for the team.

[github-actions[bot]]

This issue had no activity for 4 months, and will be closed in 2 weeks unless there is new activity. Cheers!

[natestemen]

This is related to https://github.com/unitaryfund/mitiq/issues/712.

[natestemen]

Closing this in favor of the slightly more general #712.