The question
For a network divided into two nonempty parts, which division minimizes normalized information loss? The benchmark first computes the answer by enumeration, then asks how often several search methods recover it. The word exact refers to complete search over this finite bipartition set using the stated floating-point tolerance. It does not mean exact rational arithmetic, every possible partition into any number of parts, or a complete calculation of IIT 4.0.
There are four network sizes, 8, 10, 12 and 14 nodes; three construction families, dense, modular and sparse plus ring; and five network seeds per size and family. This gives 60 instances. Fixing one node on the first side removes duplicate complementary cuts, leaving 2^(n−1)−1 candidates for each instance. The reference tables contain 163,140 candidate values in total.
The network model
Each instance is a linear stochastic recurrence with an innovation covariance equal to the identity. The recurrent matrix is scaled to spectral radius 0.9. The stationary population covariance is computed from a discrete Lyapunov equation. This avoids estimating covariance from a finite simulated time series, so the benchmark isolates the partition search from sampling uncertainty in covariance estimation.
These are small synthetic network models. They are neither trained language models nor recordings of biological neurons. The source archive stores each recurrent matrix, covariance, node permutation, objective table and selected partition, making the finite optimization problem inspectable.
What is minimized
Let S be one side and B its complement. The raw quantity compares conditional uncertainty when each part predicts itself with conditional uncertainty when the whole network predicts its next state. The normalizer is the smaller present-state differential entropy. Natural logarithms are used, so the entropies and raw information loss are measured in nats.
The minimized score J and the raw information loss at its minimizing partition are different quantities. The saved tables keep both. Variable units and the unit innovation covariance are fixed: differential entropy can change under rescaling, so the chosen normalizer is part of the objective definition. The denominator must be positive for the problem as implemented; that condition holds in the saved instances.
Recovery results
The counts below have been recomputed from the stored result records and checked against the saved objective tables. Queyranne has one deterministic run per network. Each of the other rows contains ten repetitions per network. Simulated annealing repetitions are independent searches with four restarts. QAOA repetitions are ten readout batches from one trained circuit for each network and depth; they are not ten independently trained circuits.
The primary comparisons preserve these different budgets. They describe observed recovery under the recorded protocol, rather than a universal ranking of the algorithms.
| Method | Exact recoveries | Recovery rate | Meaning of a repetition |
|---|---|---|---|
| Queyranne on normalized J | 11 / 60 | 18.3% | One deterministic search per network |
| Simulated annealing | 515 / 600 | 85.8% | An independent search with four restarts |
| Simulated QAOA, p = 1 | 410 / 600 | 68.3% | A 256-shot batch from the trained circuit |
| Simulated QAOA, p = 2 | 457 / 600 | 76.2% | A 256-shot batch from the trained circuit |
| Uniform sampling | 214 / 600 | 35.7% | 256 draws from valid partitions |
Why Queyranne is a meaningful comparison
Queyranne's guarantee applies to a symmetric submodular set function and uses a cubic number of oracle calls. An oracle call can itself be expensive. The published MIP study by Kitazono and colleagues also explored non-submodular information measures empirically; good performance on those examples was not a proof for every such objective.
The present normalized objective must be assessed on its own. The recovered benchmark's post-run diagnostic reports a submodularity violation in every one of the 60 normalized tables. It also reports that Queyranne recovered all 60 minima for the unnormalized diagnostic and that normalization changed the exact minimizing cut in 37 instances. These are post-run diagnostic results preserved in the packet. The current review verified the primary saved outcomes; it did not repeat the full diagnostic inequality scan.
What simulated QAOA does here
QAOA alternates a phase operation based on a cost function and a mixing operation, with angles selected by a classical optimizer. In this benchmark, p is the number of alternating layers. The simulated register uses n−1 binary variables because complement symmetry has already fixed the first node.
The entire cost vector is available in advance. Valid costs are scaled by the largest valid J value; the invalid all-in-one state receives cost 2. That state is included in the statevector, and invalid readout shots consume the shot budget. Parameters are selected by penalized expected cost, not by the probability of the already-known optimum. Three COBYLA restarts are attempted per depth and network. The saved termination records show that 356 of the 360 restarts ended at their evaluation budget; the fitted angles therefore should not be described as globally optimal.
The full truth table is exponential preprocessing, and constructing it already solves the reference problem. This experiment evaluates search concentration and finite-budget readout behavior. It does not supply an efficient hardware cost circuit, a scalable QUBO encoding, a quantum processor result, or evidence of quantum computational advantage. End-to-end timing must include table construction and parameter optimization, not just the inexpensive readout step.
What was checked again
The October 17 review verified 141 payload checksum entries. It checked all 60 stored minima, all 163,140 saved objective/component ratios, all 2,400 stochastic outcome records, probability normalization, optimum probabilities, and trial hit labels. An independent Gaussian calculation recomputed 227 selected partitions distributed across every network; the maximum component difference was approximately 5.15 × 10^−14.
These checks establish internal consistency of the supplied artifacts. The review did not rerun the original optimization or regenerate all networks under the original numerical environment. Recorded wall times remain measurements from that archived run. The full reproducibility archive contains the code, seeds, requirements, data, protocol and earlier validation outputs needed for a fresh replication.
What comes next
A useful continuation would vary the network families and normalization deliberately, include multiple independent parameter-training runs for each QAOA instance, report matched oracle and time budgets, and separate discovery instances from confirmatory ones. A hardware-oriented study would first need to show how the normalized objective is represented without supplying the exhaustive answer table.
The present result is already concrete: the exact reference identifies failures as well as successes, and every method is evaluated against the same saved objective. The next experiment should preserve that property while changing one clearly documented question at a time.