Cut/energy differential comparisons in base TFIM MAXCUT

This release makes the dense and streaming variants of maxcut_tfim(G) proceed to find the best cut or energy via differential with the previous best solution. (In v9.8, this was only done in spin_glass_solver(G).) With all dense and streaming cut searches now proceeding via differentials rather than absolutes, while there is a performance penalty when precision ceiling effect is reached, we eliminate the architectural barrier of relying on specific maximum precision to search for the optimal cut or energy: so long as the sign of the differential can be resolved, even for ceiling-effect differentials in themselves, we can tell the difference between a better cut and a worse-or-neutral one.

This release also fixes some confusion from v9.8 about how spin_glass_solver(G) cut and energy differentials should be handled. Further, the prior spin-glass mode conventions might have been confused and bugged: from a performance standpoint, it makes more sense if like-like connection is always interpreted as tending negative while like-unlike connections tends positive, then energy values just report with reversed sign convention on output, such that you might need to reverse your expected sign convention on edge weights, but the code should now be fully consistent in this convention.

Full Changelog: v9.8.1...v9.9.0

sha1sum results:
6ac04d5acc3dfe77ab824d5d024f4c63e3c26fe6 pyqrackising-9.9.0-py3-none-macosx_14_0_arm64.whl
33605f936c6e852d8b4b538d3f95eb0ba1192eb2 pyqrackising-9.9.0-py3-none-macosx_15_0_arm64.whl
70aecf9704882d590b6cd761ea5a1111c6fdc679 pyqrackising-9.9.0-py3-none-manylinux_2_35_x86_64.whl
f32b3600f1d482dcbd3e19ef93b411c87eb32910 pyqrackising-9.9.0-py3-none-manylinux_2_39_x86_64.whl
9e8e9c24a82df3b9746a42d5420196dbbce23bce pyqrackising-9.9.0-py3-none-win_amd64.whl
375154949035cb2526d0a304ebd26840abb69acb pyqrackising-9.9.0.tar.gz

Cut/energy differential comparisons (errata patch)

With apologies for releasing twice in a day after the point we intended for churn to stop, for DOI archival, there is a point of implementation "errata" on the v9.8.0 release: during the "reheat" phase of the Gray code search in spin_glass_solver(G) variants, differential improvements were identified correctly, but the associated absolute cut or energy was calculated incorrectly. This release debugs that single issue.

Full Changelog: v9.8.0...v9.8.1

sha1sum results:
2f144312c9c2d333b4e64e417a8aa2c8b3f66525 pyqrackising-9.8.1-py3-none-macosx_14_0_arm64.whl
ee29fe2f5ed66c6b8cd88d3600b145aed879d429 pyqrackising-9.8.1-py3-none-macosx_15_0_arm64.whl
3580f563ed8ba62f6d1cc36f1f0fdaf7569883db pyqrackising-9.8.1-py3-none-manylinux_2_35_x86_64.whl
b3d57d4df82a9696369a3bc42c431dd748fe8645 pyqrackising-9.8.1-py3-none-manylinux_2_39_x86_64.whl
c241d9842a5a1bd04c7cb2b47626a38a5098fba7 pyqrackising-9.8.1-py3-none-win_amd64.whl
58ed8ceea7d9b989e838cb60c0c0374e9f3c2a03 pyqrackising-9.8.1.tar.gz

Cut/energy differential comparisons

Throughout the dense and streaming variants of spin_glass_solver(G), we now search by cut or energy differential, expanding earlier similar improvements. This serves two purposes. One is appreciable optimization, at least for worst-case scaling, as differential calculation scales like O(n) compared to absolute value calculation in O(n^2). (The sparse solver variant, unfortunately, with its upper-triangular CSR adjacency matrix form, would only improve to O(n log n), which could still motivate the change, except that the highly non-sequential memory access pattern this entails on __global memory address space on GPU likely eats even further into the very modest potential gain.) The other reason is to keep defensive coding design patterns: if absolute cut exceeds the precision limit, search for optimum can still continue just on the basis of determining that there is any positive differential entailed by a tested change to the cut.

Note the truly preferred solution to exceeding floating point precision is to instead set environment variable PYQRACKISING_FPPOW=6 so that 64-bit floating-point precision will be used rather 32-bit. This appears to be necessary in certain cases of low autocorrelation binary sequences (LABS), for example. However, it's also preferable, from a software design standpoint, to offer the most robust and forgiving design possible for however users choose to apply a library, particularly if there is a simultaneous efficiency gain from that design choice.

Full Changelog: v9.7.8...v9.8.0

sha1sum results:
d7ed047f66e9d2943bc0a838591bec4b6cce40af pyqrackising-9.8.0-py3-none-macosx_14_0_arm64.whl
d44234c15426e1fbb7f97ba9dcdba6872ccfa0a4 pyqrackising-9.8.0-py3-none-macosx_15_0_arm64.whl
82d62610b860c276dcb8c21d59fb4fd7390d13f6 pyqrackising-9.8.0-py3-none-manylinux_2_35_x86_64.whl
d4991c501fcdc6f14d43b936bfb7f93932866ecb pyqrackising-9.8.0-py3-none-manylinux_2_39_x86_64.whl
26f5a697eb1e8f2ef8c17055c7ee9fe2b172fc35 pyqrackising-9.8.0-py3-none-win_amd64.whl
72cda4b3ab7cf3664093aefbd0cc675ace99d932 pyqrackising-9.8.0.tar.gz

Debug generate_tfim_samples()

This release fixes various bugs in generate_tfim_samples(), to bring it into line with the approach that's validated in tfim_validation.py. Now, using this function in the validation script, we have a direct test to show it is implemented correctly.

Full Changelog: v9.7.7...v9.7.8

sha1sum results:
0fc2001a463d210b44d2aad09f5d626e993e94c9 pyqrackising-9.7.8-py3-none-macosx_14_0_arm64.whl
a65d67472cb33360938f9beb1d379c2800278445 pyqrackising-9.7.8-py3-none-macosx_15_0_arm64.whl
ccc80b11f1dd47146ac7defa5e73e17e1def7d9e pyqrackising-9.7.8-py3-none-manylinux_2_35_x86_64.whl
f2b5175b32b233cd73685ad6a51a0e5e815c3588 pyqrackising-9.7.8-py3-none-manylinux_2_39_x86_64.whl
b8ee56c9a39cb0ec9247ef52283a55f86d7081c6 pyqrackising-9.7.8-py3-none-win_amd64.whl
02b62ca32218cb4ef5f071a02d2c56fb6b12a350 pyqrackising-9.7.8.tar.gz

O(n) per Gray code search iteration

Gray code search iterations on GPU have been updated to calculate cut or energy differential in O(n) time. Also, a bug has been fixed in initially "seeding" distinct Gray code search threads.

We also explored CPU-based cut/energy differential calculation in O(n) time: this doesn't appear to be particularly fruitful. Cut/energy calculation on CPU is already highly optimized and sub-O(n^2) in practice: there might be no easy further gain, here.

Full Changelog: v9.7.6...v9.7.7

sha1sum results:
da3b28744f747c4cd5616f0e1e9ae5cc40c958f6 pyqrackising-9.7.7-py3-none-macosx_14_0_arm64.whl
74d7e79caa3a0e35ad9b0221db5152a3256736dc pyqrackising-9.7.7-py3-none-macosx_15_0_arm64.whl
18a59388d653b845e992b4900301e35d3e1657d3 pyqrackising-9.7.7-py3-none-manylinux_2_35_x86_64.whl
b7c3996372c855e1d828728377865a79ab57b9b0 pyqrackising-9.7.7-py3-none-manylinux_2_39_x86_64.whl
8ccde196832bcf7568f608de09ad4d82108fd70d pyqrackising-9.7.7-py3-none-win_amd64.whl
15f72b38077a61770687d1d0cc11d41d50892691 pyqrackising-9.7.7.tar.gz

O(n) per bit flip

This can't be applied to the underlying TFIM heuristic, since that does not perform a differential update to search, but single and double bit flips in spin_glass_solver(G) can search based on cut or energy differential rather than absolute value, in O(n) complexity rather than O(n^2). (Alternatively, sparse solver variants would need to perform binary searches on the upper-triangular adjacency matrix, which, with global memory latency, would probably mostly cancel the benefit of an O(n) cut differential search on GPU.) Remaining potential targets for optimization include dense CPU/GPU Gray code search and CPU dense bit flip search.

Full Changelog: v9.7.5...v9.7.6

sha1sum results:
0ef928ad2c79d005f505289bf6ea236b714baf05 pyqrackising-9.7.6-py3-none-macosx_14_0_arm64.whl
54d320ec4808bf69e8ec39b7eb12f6fbdd116030 pyqrackising-9.7.6-py3-none-macosx_15_0_arm64.whl
e306a6c051d3650eee124c56e005560a700232dd pyqrackising-9.7.6-py3-none-manylinux_2_35_x86_64.whl
112528d07c605575a01ab6c7fe7b72a4243a5b65 pyqrackising-9.7.6-py3-none-manylinux_2_39_x86_64.whl
6bc8ff483a708888df990d1fa6c398f994471dbf pyqrackising-9.7.6-py3-none-win_amd64.whl
0f7cac7d2032707e426e52c175ef04754fcdc070 pyqrackising-9.7.6.tar.gz

OpenCL Gray code search

While this is a "patch" release, because it offers no new semantic "feature" in the API (or breaking API change), it is a major advancement: the Gray code search in spin_glass_solver(G) and spin_glass_solver_sparse(G) have been updated to optionally use OpenCL. This was made possible after we realized improvements in the CPU-based Gray code search that allowed us to work with a single "seed" bit string copy per thread while proceeding in a "stateful" manner to follow the energy gradient, which was actually finally an algorithm that could be ported to GPU.

Maintenance releases will follow as necessary, but, having converted all major sources of execution time overhead to accelerated OpenCL code, pyqrackising might be truly "complete" as an open-source project. (Of course, the authors do not intend or want to just "drop the project cold," at all, but there appears to be little room left for improvement on the base concept, at least for now.)

Full Changelog: v9.7.4...v9.7.5

sha1sum results:
f64df24669a5748c269caa889c0a734f1288914b pyqrackising-9.7.5-py3-none-macosx_14_0_arm64.whl
dea12c282682e2538c49a4ce091c08bfcd6a5ac7 pyqrackising-9.7.5-py3-none-macosx_15_0_arm64.whl
db1f71eb029275cd8ed51028ca227e4eed82d2c9 pyqrackising-9.7.5-py3-none-manylinux_2_35_x86_64.whl
e1314834812631fec8106ce1462cb780907b39f7 pyqrackising-9.7.5-py3-none-manylinux_2_39_x86_64.whl
fc64fa636fed919c60896f6d8675267617bf7dd8 pyqrackising-9.7.5-py3-none-win_amd64.whl
2000fc02ee00bff89bf52e8a72c05d30edf1bca9 pyqrackising-9.7.5.tar.gz

Final micro-optimization pass ("complete" project status candidate)

In this release, we fix an edge case for negative h parameter values, and we make a final pass at "micro-optimization" on Gray code searches. (GPU-based Gray code search was privately drafted, but the "statefulness" of the CPU-based version makes it a challenging or bad candidate for adaptation to GPU, while replacing "statefulness" with an "embarrassingly parallel" implementation would seem to require an exponential growth in resources for comparable productive coverage of the search space, at least for MAXCUT problems significantly larger than 64 nodes.)

We have no intention of "abandoning" this software, by any means, but, being relatively small in its overall development scope, it might now be a "complete" open-source software project: besides near-ideal raw transverse field Ising model (TFIM) heuristics, we've successfully engineered "hard problem" solver interfaces on top of adiabatic (and "out-of-time-order correlation," "OTOC") TFIM to expose real, utility-scale, "quantum-inspired" approaches to MAXCUT and Traveling Salesman Problem that tend to outperform Goemans-Williamson and Christofides at large scales. With performant dual CPU and GPU implementations for all appropriate solvers, we've already reached the limits of the intended scope, except in exploring the library's potential applications.

(We're honestly eager to continue development, and we will stay abreast of the literature to respond to new, relevant claims of "quantum advantage," but, until then, and even at such points in time, the research might be in application rather than development of new library features.)

Full Changelog: v9.7.3...v9.7.4

sha1sum results:
f083a66e6263bfc275bc591ad05bd81363c3e771 pyqrackising-9.7.4-py3-none-macosx_14_0_arm64.whl
9287490e5002a01dfe505476d17c52b48b4581c4 pyqrackising-9.7.4-py3-none-macosx_15_0_arm64.whl
f99882d082848de9cb27371b8afe0c8d5cbbd40b pyqrackising-9.7.4-py3-none-manylinux_2_35_x86_64.whl
08c96e81f0974644a352db11e9f647bb06c3d90f pyqrackising-9.7.4-py3-none-manylinux_2_39_x86_64.whl
3f3812c966c0b39eae70e72656646e25c85c73db pyqrackising-9.7.4-py3-none-win_amd64.whl
a2e25cdf181be1c506720aed24ff38bbd37d06cd pyqrackising-9.7.4.tar.gz

Add citation in README and fix edge cases for t=0

This incremental patch release adds a clear and specific (arXiv hyperlink) reference to the relevant report from Quantinuum that indirectly inspired our TFIM heuristics, during experimental recreation in simulo. We also analytically insert the correct behavior for TFIM when t=0, which is the only discontinuous point (or rounding neighborhood) for which the heuristic seems to fail, but the behavior there is always known analytically without significant computational overhead and can always be inserted by hand without discontinuity.

Full Changelog: v9.7.2...v9.7.3

sha1sum results:
a369f4b498db0d1a0288641927fd49a55cd4be96 pyqrackising-9.7.3-py3-none-macosx_14_0_arm64.whl
4e10e90c9086eb71424d3d83029ff65173df29e5 pyqrackising-9.7.3-py3-none-macosx_15_0_arm64.whl
fb0ef242babeed0169c9f885835fdb0e97bb93e6 pyqrackising-9.7.3-py3-none-manylinux_2_35_x86_64.whl
a17a92ef58d82b77df5dd7aeb2d8ade1c44a03b1 pyqrackising-9.7.3-py3-none-manylinux_2_39_x86_64.whl
54daace8733905440d17e1c86f77c5b03fbb6b24 pyqrackising-9.7.3-py3-none-win_amd64.whl
35ac038d7eee4bab5cf751931bd1b7f2d69e9316 pyqrackising-9.7.3.tar.gz

Improve documentation for DOI request

This release adds an overview of the transverse field Ising model (TFIM) heuristic theory, motivation, and design content to the README, for archival as a Zenodo DOI.