BDT as QPager "global qubits"

[WrathfulSpatula]

A single QPager "global qubit" is basically the same thing as a QBinaryDecisionTree "node," if the "global qubit" additionally has a normalized pair of scale factors for its two branches. By giving the QPager global qubits an explicit class identity, with two scale factors apiece whose norms sum to 1, some amazing opportunities emerge. These kinds of global qubits will keep pointers to their pages, and the pointers can be manipulated directly, like replacing 2 entire pages with 2 pointer references to the same page, when the two are identical. To work this way, we keep the pages internally normalized, to total norm of 1 apiece, which might simplify the QPager implementation overall.

When we "shuffle" pages for inter-page operations, I can write an OpenCL kernel that does the shuffle and two scale factor applications in the same traversal, I think, so there's not a major performance penalty, there. This is also stepping-stone work toward generalized binary decision trees, which I will ultimately use as a layer over QStabilizerHybrid.

QBinaryDecisionTree hasn't seen much use in itself, yet, but it does the work of QPager global qubits better than what we already use. I'm excited by the prospect!

[WrathfulSpatula]

First, to do this, NormalizeState() in QInterface should accept an additional phase argument, to apply to the normalization constant:

virtual void NormalizeState(real1_f nrm = REAL1_DEFAULT_ARG, real1_f norm_thresh = REAL1_DEFAULT_ARG, real1_f phaseArg = ZERO_R1)

I considered combining the normalization constant with the phase argument at first, but the two really are logically separate. Leaving a default argument for nrm will lead to its automatic calculation, while this is still entirely independent of phaseArg, which can be applied as the complex angle at the same time. Leaving them separate also prevents confusion as to whether phaseArg should be transformed from its input form the same way as the nrm argument, which results in the application of ONE_R1 / std::sqrt(nrm) as the actual directly multiplicative constant, before we multiply it by std::polar(ONE_R1, phaseArg).

[WrathfulSpatula]

This might basically work as a QPager alternative at this point, but the tradeoff seems to be marginally reduced RAM footprint for much longer execution time.

A note about the extension to QBdt over QStabilizer: similar to how QBdt decomposes quantum gates to simplify its simulation algorithm, the quantum teleportation algorithm could be used to move entangled stabilizer qubit states into QBdt, (except that it is non-unitary in ancillae, which has been universally avoided in the design of Qrack QInterface methods).

[WrathfulSpatula]

QBdt over QEngine is fully implemented, at this point. We'd like QUnit to operate over this, but, first, it's more important to implement the equivalent for QBdt over QStabilizer. QBdt over QEngine can reduce "paging" footprint, but the limiting factor seems to be specifically whether there is entanglement between "global" (QBdt) and "local" (QEngine) qubits. This would be much more effective for QStabilizer "local" qubits, since it opens up interoperability between Clifford/Pauli stabilizer qubits with a limited number of universal qubits, where the exponentially duplicated base unit would scale like the square of qubits instead of the power of 2 of qubits.

[WrathfulSpatula]

I've generalized the implementation to potentially Attach() all QInterface types under QBdt! This will make extended stabilizer much easier to implement in this manner, as QStabilizerHybrid is now a valid type to Attach() under QBdt. It just becomes a matter of managing qubits for gates that exceed Clifford/Pauli operators, and "dumping" to state vector at the right point.

With that in place, it's a relatively safe bet that I'll have extended stabilizer done by the end of the coming weekend. Hopefully, this will become part of the default optimization layer stack, with QBdt inserted under QUnit with a QBdt::Attach() call for QStabilizerHybrid.

[WrathfulSpatula]

QBdt passes all unit tests as a bare top layer and under QUnit. It's time to use it for extended stabilizer.

QBdt can already accept a QStabilizerHybrid instance via Attach(), as long as the attachment is a QInterface. However, the best (and ultimately easiest) leverage point seems to be to sandwich QBdt under QStabilizerHybrid and above QStabilizer, which is Qrack's raw Aaronson CHP adaptation, before inheritance from QInterface.

There doesn't seem to be any practical benefit in requiring QBdt over QPager or QHybrid, for example, though QBdt could functionally replace the QPager layer, were it performant for the role. Placing QBdt in-between (restricted instruction stabilizer tableau) QStabilizer and (universal interface) QStabilizerHybrid layers also avoids the need to wrap layers for any non-stabilizer ket simulation at all. Further, it directly serves the intended "hybridization" of QStabilizerHybrid, (between "RISC" efficiency and universal quantum computational gate interface).

[WrathfulSpatula]

QBdt can be the layer for "managing 'magic,'", in terms of T gate and minimal universal qubits, based on throwing not-implemented exception from stabilizer and handling fallback, upon request for gate operation. More generally, QBdt could be built to assume that a QBdtAttachment (passed to Attach()) might arbitrarily lack elements of a universal or general gate set, throwing exception from Mtrx() and MCMtrx() calls, since QBdt can "absorb" and replace non-universal qubits with its own type, (in a quantum binary decision tree).

[WrathfulSpatula]

We have an implementation that works in a satisfactory way for many applications, at this point. In my (currently local copy, hacked-up for the specific case) unit tests, a QEngine based "attachment" under QBdt passes our entire suite for QInterface methods with the specific exception of arithmetic logic unit methods, (QAlu,) "parity" methods, (QParity), and Schmidt decomposition methods, which is expected and acceptable. Even QStabilizer passes the same tests, except for test_sqrtxconjt at low enough "magic qubit" couunt, which might be a "dumb mistake," or it might be a singular point for QStabilizer under the Attach() API.

However, following through with quantum binary decision trees method, the QBDT node PushStateVector() implementation cut in 9816335 seemed obviously necessary at that point in development, and I'm not still not convinced that it isn't. The reason this was cut was that we don't push to the tree depth where the heterogeneous attached PushStateVector() implementation is invoked, but maybe we must. I am investigating, this weekend.

[WrathfulSpatula]

Running test_mirror_quantum_volume again with a universal simulator attachment, there's definitely still (or newly) a bug here in about this region of the code. It might be as simple as appropriately reinstating the code from the commit linked above, and finding a workaround for stabilizer that avoids certain QInterface method usage.

[WrathfulSpatula]

This works, but it's slow in practicality. However, the issue has been addressed, so we can close the ticket.