Compressed state vectors

[WrathfulSpatula]

This specifically will not be in the January 1st release, but (conventional compression algorithm) state vector compression could probably add at least a qubit or two to maximally entangled capacity on any given system, if at significant speed cost. QUnit is already a Schmidt decomposed representation of state, which reduces RAM needs, but QEngine type sub-unit state vectors typically must have far less Shannon entropy per float than type capacity, by simple considerations, compressed with even just a ZIP algorithm, for example.

I'm sure much has been said and done on this front by other parties already, but part of this issue is researching those approaches. For Qrack, a compressed QEngine type would still synergize with QUnit's capabilities. We might subclass QEngineCPU, with a corresponding new subclass of StateVector, or perhaps we could get away with just the StateVector subclass and a configuration option for QEngineCPU. Since we've introduced "hybrid" types, both QEngineCPU and QEngineOCL efficiency effectively contribute together to overall simulator performance, but GPU compressed state vectors are a little daunting, for the moment, and might not pay.

[WrathfulSpatula]

I know that work has been seemingly ill-fated, so far, but I might make sense to start by reviving QPager, in part to apply toward this end. We haven't seen practical return from it, yet, (or even 100% stability,) but compressing and decompressing per page might be a good starting point for avoiding the need to fully decompress an entire state vector at once, which could otherwise prevent any qubit capacity extension by this method.

[WrathfulSpatula]

QPager has been dug out of the commit history, debugged, and optimized. Now is probably a good time to look into compressing "pages" under QPager, for the next few days. I'd like QPager to first give a practical return over the same layer stack without QPager as a layer, but, failing that, at least we might increase the maximum possible number of qubits that can be simulated (with a significant execution time premium) on any system using "paging."

[WrathfulSpatula]

https://github.com/glampert/compression-algorithms looks like a great (public domain) source for implementing this. I'm anticipating that QEngineCPU and QEngineOCL need Compress() and Decompress() methods that convert their respective state vector types to and from the output format of the algorithms in that library, likely with Huffman compression or some combination of algorithms. QPager would call these methods on pages, calling Decompress() before a page is modified by a gate, and Compress() when done. Uncompressed state vectors should be set to null after a compressed state vector is produced, and vice versa. QPager dispatches partial gates on pages in parallel, which might lead it to reach peak memory usage with every page fully decompressed, which would defeat the purpose, but likely this can be tackled with a constructor option in QPager that activates compression in the QEngine types and restricts to one page decompressed per node context (or overall) at a time.

[WrathfulSpatula]

For the Unitary Fund Hackathon, this is the advanced difficulty, "extra credit" issue option I'd suggest.

It is not necessary to be able to operate gates or logic on compressed state vectors, but, using a standard compression algorithm under appropriate open source licensing, we should implement the Compress() and Decompress() methods, and not expect to be able to do anything but Decompress() an already-compressed state vector, for now. It's acceptable to limit to QEngineCPU, and we can leave OpenCL compressed state vectors for later. QPager should have a constructor option to let it know to Compress() and Decompress() QEngineCPU "pages" under it. (One acceptable approach would be to add these abstract methods to QEngine and just pass through to empty implementations in QEngineOCL, for now. If you want to add OpenCL kernels for compression and decompression, that would be heroic, but it might outsize this issue. I'll help coordinate if this leads to a merge conflict with #591.)

If all QInterface sub-classes were to know to internally Decompress() if necessary when a gate method is called, this would fit the Qrack paradigm, of a state machine that transparently knows how to manipulate its own state based on context of any method being called at the immediate present. Knowing a rough sense of the scope of that, as a requirement, it's not necessary, but it's a very nice design feature to ultimately have.

External dependency and licensing is a high priority concern for vm6502q/qrack, where our only required external dependency forever has been C++11 standard! We're proud of that, and we want to keep it that way. The compression algorithms repository linked above looked good, for the purpose, but you're free to use anything with LGPL compatible licensing that preferably doesn't become a required external dependency, (but it can be an optional external dependency, alternatively, or an LGPL compatible licensed internal source inclusion).

[WrathfulSpatula]

Per a talk I saw at QCE'21by Robert Wille, binary decision trees might be a great way to approach compressed state vector that can be directly operated on. He also said, when pressed, that binary decision trees aren't necessarily limited by entanglement, (if we think of states with all permutations with equal probability but a few binary decision phase factors, for example,) whereas Qrack's Schmidt decomposition is fundamentally limited by high entanglement.

I think we should experiment with (rank 1) ket-based binary decision trees, to compress the high-entanglement states that filter down to ket or QEngine level after Schmidt decomposition attempts, (and after stabilizer hybridization). At first, this would be a CPU-only alternative ket representation option. If we needed to start from a ket, we could compare adjacent parallel pairs of ket amplitudes for difference up to overall scalar factor, and compress in parallel pairwise from bottom up.

[WrathfulSpatula]

As discussed above, QBinaryDecisionTree has been implemented in #900. This isn't yet up to performance standards, but the new QInterface sub-type is stable, and it at least slightly resembles some other conventional compression algorithms, (besides Schmidt "decomposition," as opposed to "compression").

[WrathfulSpatula]

QBdt works well, for certain cases. However, when QPager transfers between devices, the simulation becomes bus-bandwidth-limited. As we have methods that convert between QBdt and state vector representations, we'd like to implement them on GPU, to compress (half-)pages before QPager transfers them between devices.