Pith. sign in

REVIEW 4 major objections 4 minor 63 references

The paper argues that quantum compilers should minimize both run-time gate cost and the description length of the emitted circuit, and demonstrates on SU(2) that the joint optimum can be a decomposition that is neither the shortest nor the

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-07-31 23:20 UTC pith:WA3SXRV2

load-bearing objection The formal idea of pairing circuit cost with description cost is worth a look, but the headline 0.3% split effect is a product of beta calibration and bzip2 quantization, not a proven signal. the 4 major comments →

arxiv 2607.23990 v1 pith:WA3SXRV2 submitted 2026-07-27 quant-ph cs.ET

DeComp2: Description Complexity aware Decomposition

Aritra Sarkar This is my paper
classification quant-ph cs.ET
keywords quantum compilationdescription complexityKolmogorov complexitycircuit complexityminimum description lengthunitary decompositiongate set enumerationcompiler objective
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

DeComp2 claims that the standard quantum-compiler objective, minimizing gate count or depth, conflates two resources: what the quantum substrate does at run time and what must be said to describe the circuit. The paper proposes minimizing an additive total C_tot = α·C_circ + β·C_Kol, pairing circuit complexity with a Kolmogorov-style description complexity of the emitted gate sequence. On a deterministic Haar-representative grid of single-qubit unitaries, exhaustive H/T enumeration shows the two cost axes are not tightly functionally related, and for 59 of 20,327 covered targets the joint minimizer differs from both per-axis minimizers. A worked example (target (41,10)) has a joint optimum at an 11-gate, 320-bit candidate that is neither the shortest (10 gates, 336 bits) nor the most compressible (12 gates, 312 bits) string in the tolerance ball. If correct, this means gate-count-only optimizers silently absorb description-side penalties and motivates description complexity as an active compiler objective.

Core claim

For a fixed target unitary inside an approximation tolerance, there can be many H/T decompositions of different lengths. The paper's central empirical discovery is that the minimizer of the additive total C_tot = α·C_circ + β·C_Kol can sit strictly between the gate-count minimizer and the compression minimizer: at the Fibonacci-grid target (41,10), the joint optimum is the 11-symbol word (320 compressed bits), while the shortest word has 10 symbols (336 bits) and the most compressible has 12 symbols (312 bits). This exhibits, in the smallest non-trivial case, the compilation choices a C_circ-only optimizer discards.

What carries the argument

The carrying mechanism is the additive cost objective C_tot(U) = α·C_circ(U) + β·C_Kol(U), with C_circ the minimum weighted gate length and C_Kol the length of the shortest program (upper-bounded by compression surrogates bzip2 and pybdm) that emits the gate sequence. The paper maps this decomposition onto the positional/kinetic entropy split of the second law of quantum complexity, and uses exhaustive enumeration of all H/T strings up to length 12 over a Fibonacci-lattice axis grid and inverse-CDF Haar angle grid to produce (C_circ, C_Kol) pairs for 32,768 targets.

Load-bearing premise

The central phenomenon depends on the empirical exchange weight β = 0.07 (fit by sweeping to maximize split count, not derived) and on compression-based surrogates faithfully tracking true description complexity at string lengths of 10–12 symbols—if either fails, the 59 split targets may be artifacts of calibration and compressor quantization.

What would settle it

Run the same exhaustive enumeration on the same 20,327 covered targets with β replaced by a value from a unit-fixing argument (e.g., equating one HT symbol with one description bit) and count how many targets have arg min C_tot distinct from both per-axis minima; if that count falls to zero, the reported effect is an artifact of the calibrated β. Alternatively, apply bzip2 to random 10–12 symbol strings over the same alphabet: if the bit-length distribution overlaps the 312–336 bit range used to exhibit the trade-off, the split signal is within compressor noise.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • A C_circ-only optimizer, asked to break ties inside an ε-ball, will make the wrong choice on the ~0.3% of covered targets where the additive optimum is split; the paper calls this fraction 'operationally meaningful.'
  • Raising the enumeration cap M, using denser gate sets (e.g., Clifford+T with native S), or moving to multi-qubit circuits is expected to raise the split fraction, since denser ε-balls offer more internal trade-off.
  • The additive objective acts as a minimum-description-length regularizer over the otherwise degenerate set of C_circ-minimizers, giving a principled way to arbitrate among equally short decompositions.
  • A hierarchical representation that exposes loops and macros lowers C_Kol without changing unrolled C_circ, so integrating C_Kol into the compiler IR could enable macro discovery, gadget extraction, and controller-side bandwidth savings.
  • Both surrogates are upper bounds on true Kolmogorov complexity, so the appearance of distinct minima under a coarse compressor establishes the effect in its most conservative form.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The reported split count is produced by calibrating β = 0.07 via a sweep that maximizes splits; at α = β = 1 the description term dominates and splits drop to zero, so the phenomenon's visibility depends on the chosen exchange rate, not only on the geometry of the cost landscape.
  • Because bzip2 outputs are multiples of 8 bits and the strings are only 10–12 symbols, the '8-bit saving' that exhibits the trade-off sits within the compressor's quantization granularity; a null baseline on random strings of the same length would be needed to confirm the signal is not compressor noise.
  • Read through the paper's own related-formalism connections, C_tot is equivalent to a maximum-a-posteriori objective under a speed prior or a Gibbs ensemble over programs, which suggests the weights α and β could be derived from a unit-fixing argument rather than swept—an extension that would make the effect less calibration-dependent.
  • A direct testable extension is to apply the same C_tot-guided search with a learned dictionary or a decompilation step that recovers loops; if hierarchical representations systematically move the joint optimum away from the flat gate-count optimum on more than 0.3% of targets, the case for C_Kol as an active compiler signal strengthens.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper proposes replacing the standard execution-only quantum compilation objective with a life-cycle objective C_tot = α·C_circ + β·C_Kol, where C_circ is gate-count-like circuit complexity and C_Kol is a Kolmogorov-style description complexity of the emitted gate sequence. It instantiates this on SU(2) by exhaustive HT-string enumeration with bzip2 and pybdm as tractable surrogates for C_Kol. The central empirical claim is that C_Kol carries information not contained in C_circ: the two surrogates correlate with C_circ but break its rank order, and for 59 of 20,327 covered targets the joint minimizer differs from both the per-axis minimizers, with a worked example (k,j)=(41,10) where the C_tot-minimizer is neither the shortest nor the most compressible string in the ε-ball. The paper argues this motivates C_Kol as an active co-objective for hierarchical compiler IRs.

Significance. If the central claim were established, the paper would provide a concrete, reproducible demonstration that a description-complexity term can change the output of a quantum decomposer in a way a gate-count-only optimizer would miss, with direct implications for hierarchical compiler IRs, macro discovery, and controller-side compression. The paper has genuine strengths: a deterministic, reproducible target ensemble; exhaustive enumeration with a disclosed enumeration cap; an open-source implementation; and a well-posed empirical framework in the candidate-level analysis of §3.4. However, the formal objective as written in Eq. (10) is internally inconsistent with the empirical joint-minimization procedure, and the main empirical phenomenon rests on a calibrated weight and a single coarse compressor without a null baseline. These issues are load-bearing for the paper's core assertion.

major comments (4)
  1. [§2.3, Eq. (10)] Eq. (10) defines C_tot as a sum of two independent minima: α·min over gate sequences of the weighted gate count plus β·min over programs p whose output realizes the unitary. As written, this is not the joint cost of a single decomposition; it is the sum of two separate per-axis optima, and no trade-off between C_circ and C_Kol can occur within the formula. The empirical analysis in §3.4 instead correctly evaluates each candidate string s (or program p) individually and computes α·C_circ(s)+β·C_Kol(s) before minimizing over candidates. The formal definition must be corrected to something like C_tot(p)=α·C_circ(seq(p))+β·|p|, with minimization over programs p (or strings) that realize U. This is not a cosmetic issue: the central claim of distinctness of joint versus per-axis minima is not supported by the equation as printed.
  2. [§3.4 and §3.5] The entire existence of the 59 split targets is a consequence of the calibration of β. The paper states that at α=β=1 the description term dominates and the split count drops to zero, and that a logarithmic sweep over β exposes a plateau β∈[0.063,0.086] on which the split count is stable at 59. The paper discloses that β=0.07 is 'empirical, not principled,' but this does not remove the circularity: the phenomenon is being fitted into existence. To make the claim load-bearing, the authors must provide a principled derivation of β (e.g., equating the cost of one HT symbol with one description bit on a fixed reference machine) or, failing that, a robustness analysis showing that a non-trivial split fraction persists over a wide, independently justified range of β and is not maximized by construction. Without this, the 59 targets are not evidence that C_Kol carries information beyond C_circ;
  3. [§3.5 and §3.2, bzip2 surrogate] The empirical demonstration is built on bzip2 outputs for 10–12-symbol HT strings, which are 312–336 bits, i.e., 39–42 bytes. The reported 8-bit saving that the joint minimizer trades for a +1 C_circ penalty is a single 8-bit quantization step of bzip2, not a fine-grained description-length difference. The paper concedes in §3.5 that bzip2 is coarse, but the paper does not provide the essential null baseline: compressing random binary strings of the same lengths and performing the same β sweep. Without such a baseline, rank breaks and apparent 'splits' cannot be distinguished from compressor noise plus weight tuning. The pybdm surrogate is mentioned but no correlation coefficient, split count, or analogous worked example is reported, so the claim rests almost entirely on the bzip2 surrogate. This is a load-bearing gap because if random strings produce a similar split fraction under the s
  4. [§2.3 vs §3.4] The text in §2.3 states 'α=β=1 is considered throughout this note, deferring weight calibration to a deployment-level concern.' This directly contradicts the calibration in §3.4, where (α,β)=(1,0.07) is adopted and all split results, including Figure 4, use β=0.07. This inconsistency affects the reproducibility of the experiments as described; the reader cannot tell from the main text which weights are actually used in which figure.
minor comments (4)
  1. [Abstract and §2.3] Several typos and incomplete sentences: 'The mirrors the additive positional and kinetic entropy' is missing a subject; 'motivating C_Kol as an active optimization signal for hierarchical intermediate representation for compiler' is missing an article; 'arg minC circ is highly degenerate, with many equally short decompositions' reads as a run-on. These should be cleaned up.
  2. [§3.4, Eq. (13)] The condition 'arg min_s C_tot(s) ≠ arg min_s C_circ(s) ≠ arg min_s C_Kol(s)' is an ambiguous chain of inequalities. It should be written as three pairwise inequalities, e.g., 'arg min C_tot ≠ arg min C_circ and arg min C_tot ≠ arg min C_Kol and arg min C_circ ≠ arg min C_Kol,' to avoid misinterpretation.
  3. [§3.3, Figure 2] The caption and text report Pearson r≈+0.7 for bzip2 but give no analogous statistic for pybdm. Since the independence claim is made for 'both surrogates,' the pybdm correlation and any rank-break fractions should be reported explicitly.
  4. [§3.2.2 and refs [30,49]] Some referenced preprints (e.g., [30], [49]) are dated 2026 and may not be publicly available at the time of review; the authors should verify the references are accessible and correctly cited. Also, the 'pybdm' block-decomposition method is cited but not described; a one-sentence explanation would help the reader.

Circularity Check

1 steps flagged

The split-target evidence is an artifact of beta calibration, though the rank-order independence claim is not circular.

specific steps
  1. fitted input called prediction [§3.4 (Eq. 13) and §3.5 Discussion]
    "With α=β=1 on bzip2 bits and HT-lengths the description term dominates by more than an order of magnitude, the joint minimizer collapses onto arg min C_Kol, and the split count drops to zero. We therefore calibrate (α,β) so the two surrogates contribute on comparable absolute scales. A logarithmic sweep over β∈[10^{-3},10] with α=1 exposes a plateau β∈[0.063,0.086] on which the split count is stable at 59 targets. We adopt (α,β)=(1,0.07) as the representative point for downstream results."

    The paper's concrete evidence that C_tot changes compiler choices is the existence of split targets (Eq. 13) and the worked example at (11,320). But β, which defines C_tot, was chosen by sweeping exactly the split-count statistic and adopting a plateau that maximizes it, after noting that at α=β=1 the split count is zero. The reported 59 split targets and the joint minimizer distinct from both per-axis minimizers are therefore a by-construction consequence of the calibration, not an independent empirical confirmation. The paper's own §3.5 concedes: "the weight β=0.07 is empirical, not principled. It was selected as the plateau value of a sweep that maximizes the split count." The rank-order independence claim in §3.3 remains β-independent, so the circularity is partial but real.

full rationale

The formal objective (Eq. 10) is not circular: it is an explicit additive combination of an execution proxy and a description surrogate, motivated by—but not deduced from—the Brown-Susskind second-law decomposition, and the related-formalisms section honestly maps it onto Levin complexity/MDL rather than claiming novelty. The independence claim in §3.3 also is not circular: bzip2/pybdm lengths of enumerated HT strings are computed from the strings, not from the integer HT length, so the rank-order break is an empirical scatter property, even though its interpretation is limited by compressor granularity. The circularity is localized to the calibration of β in §3.4: β is chosen by sweeping the exact split statistic that is then reported as the paper's concrete evidence that C_tot changes compiler choices, and the paper concedes the weight is empirical and selected to maximize split count. Thus the 59 split targets and the (11,320) example are constructed by the weight choice, not independently predicted. No load-bearing self-citation was found: the cited EQISA/DeQompile/EO-GRAPE self-works are used as related work and implementation context, not as the justification for the additive objective or the empirical result. The bzip2 quantization and absence of a random-string null are construct-validity concerns, not circularity.

Axiom & Free-Parameter Ledger

6 free parameters · 5 axioms · 0 invented entities

No new physical entities are introduced; the S_pos/S_kin mapping is an analogy, not a postulated mechanism. The paper's genuine add-ons are the calibrated weight β and the surrogate assumptions listed above.

free parameters (6)
  • β (description-weight) = 0.07 = 0.07
    Chosen on a sweep plateau β∈[0.063,0.086] that maximizes the split count (§3.4). The central empirical phenomenon (59 split targets) only exists in this window; at α=β=1 the split count is 0. The paper labels it 'empirical, not principled.'
  • α (circuit-weight) = 1 = 1
    Fixed by convention, not calibrated (§2.3).
  • approximation tolerance ε = 0.15 = 0.15
    Experimental hyperparameter; at (x,y,M)=(512,64,12) it yields 62% coverage; the split fraction depends on ball density and hence on ε (§3.2.1).
  • enumeration cap M = 12 = 12
    Fixes the 8190-string scan and hence the ε-ball contents; the paper predicts split fraction rises with M (§3.5).
  • grid sizes (x,y) = (512,64) = 512,64
    Target-grid sizes chosen for tractability; 32,768 targets, 20,327 covered (§3.2.1).
  • per-gate weight ℓ(g) = 1 = 1
    Uniform HT gate weight; the paper motivates locality-weighted ℓ(g) but does not implement it (§2.1).
axioms (5)
  • domain assumption Compression length (bzip2/pybdm) is a valid upper-bound surrogate for the Kolmogorov complexity C_Kol of short HT strings
    Used throughout §3 to define C_Kol surrogates in Eq. 11-12; a null baseline on random strings is never provided, so the surrogate's sensitivity for 10-12 symbol inputs is unverified.
  • domain assumption The H/T gate set with tolerance ε provides a valid discrete approximation to SU(2)
    Solovay-Kitaev guarantees existence (§2.1), but the empirical coverage is only 62% at M=12, so the split analysis runs on a subset of targets (§3.2.1).
  • domain assumption The Fibonacci-lattice axes plus inverse-CDF angles reproduce the Haar measure on SU(2) well enough for the conclusions
    Sanity-checked against uniform quaternions in Figure 1; the deterministic ensemble removes sampling noise but also removes any estimate of its own variance (§3.1).
  • domain assumption The Brown-Susskind additive S_pos + S_kin decomposition is an appropriate design principle to lift into a compiler objective
    §2.2; the paper explicitly does not rely on the monotonic complexity-growth conjecture, but the additive ledger is borrowed from a physics context without independent justification for the compiler setting.
  • standard math Almost all binary strings are algorithmically incompressible (counting argument)
    Invoked in §3.5 to explain why C_circ-optimal decompositions are typically near-maximal in C_Kol; standard result (Li-Vitányi [22]).

pith-pipeline@v1.3.0-alltime-deepseek · 14630 in / 19890 out tokens · 180337 ms · 2026-07-31T23:20:16.880569+00:00 · methodology

0 comments
read the original abstract

Quantum compilers optimize execution-only proxies such as gate count, depth, and fidelity, treating the compiled circuit as the unit of cost. This conflates two distinct resources, how much the substrate has to do at run time, and how much has to be said to describe what to do. Unrolling a looped program leaves run-time cost unchanged while erasing the hierarchical structure on which downstream optimization and reuse rely. We propose lifting the compiler objective from execution to life cycle complexity by pairing the circuit complexity $\mathcal{C}_{\mathrm{circ}}$ with a Kolmogorov-style description complexity $\mathcal{C}_{\mathrm{Kol}}$ of the emitted circuit, and minimizing the additive total $\mathcal{C}_{\mathrm{tot}} = \alpha\,\mathcal{C}_{\mathrm{circ}} + \beta\,\mathcal{C}_{\mathrm{Kol}}$. The mirrors the additive positional and kinetic entropy of the second law of quantum complexity, and reads as a minimum-description-length regularizer over the otherwise degenerate set of $\mathcal{C}_{\mathrm{circ}}$-minimizers. We instantiate the objective on $SU(2)$ through exhaustive HT-enumeration with compression-based surrogates upper-bounding $\mathcal{C}_{\mathrm{Kol}}$. Across a Haar-representative target grid the two surrogates correlate positively with $\mathcal{C}_{\mathrm{circ}}$ yet break its rank order on a non-trivial fraction of points, ruling out a tight functional dependence. With calibrated weights the joint cost selects, for a small but operationally meaningful fraction of targets, a candidate that is neither the shortest nor the most compressible HT-string in the $\varepsilon$-ball, exhibiting the compilation choices a $\mathcal{C}_{\mathrm{circ}}$-only optimizer discards and motivating $\mathcal{C}_{\mathrm{Kol}}$ as an active optimization signal for hierarchical intermediate representation for compiler.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

63 extracted references · 9 linked inside Pith

  1. [1]

    Modeling by shortest data description.Automatica, 14(5):465–471, 1978

    Jorma Rissanen. Modeling by shortest data description.Automatica, 14(5):465–471, 1978

    1978

  2. [2]

    Second law of quantum complexity.Physical Review D, 97(8):086015, 2018

    Adam R Brown and Leonard Susskind. Second law of quantum complexity.Physical Review D, 97(8):086015, 2018

    2018

  3. [3]

    Holographic complexity equals bulk action? Physical review letters, 116(19):191301, 2016

    Adam R Brown, Daniel A Roberts, Leonard Susskind, Brian Swingle, and Ying Zhao. Holographic complexity equals bulk action? Physical review letters, 116(19):191301, 2016

    2016

  4. [4]

    Computational complexity and black hole horizons.Fortschritte der Physik, 64(1):24–43, 2016

    Leonard Susskind. Computational complexity and black hole horizons.Fortschritte der Physik, 64(1):24–43, 2016

    2016

  5. [5]

    Linear growth of quantum circuit complexity.Nature Physics, 18(5):528–532, 2022

    Jonas Haferkamp, Philippe Faist, Naga BT Kothakonda, Jens Eisert, and Nicole Yunger Halpern. Linear growth of quantum circuit complexity.Nature Physics, 18(5):528–532, 2022

    2022

  6. [6]

    The solovay-kitaev algorithm.arXiv preprint quant-ph/0505030, 2005

    Christopher M Dawson and Michael A Nielsen. The solovay-kitaev algorithm.arXiv preprint quant-ph/0505030, 2005

    Pith/arXiv arXiv 2005

  7. [7]

    A geometric approach to quantum circuit lower bounds.arXiv preprint quant-ph/0502070, 2005

    Michael A Nielsen. A geometric approach to quantum circuit lower bounds.arXiv preprint quant-ph/0502070, 2005

    Pith/arXiv arXiv 2005

  8. [8]

    Quantum computation as geometry.Science, 311(5764):1133–1135, 2006

    Michael A Nielsen, Mark R Dowling, Mile Gu, and Andrew C Doherty. Quantum computation as geometry.Science, 311(5764):1133–1135, 2006

    2006

  9. [9]

    Optimal control, geometry, and quantum computing

    Michael A Nielsen, Mark R Dowling, Mile Gu, and Andrew C Doherty. Optimal control, geometry, and quantum computing. Physical Review A—Atomic, Molecular, and Optical Physics, 73(6):062323, 2006

    2006

  10. [10]

    Optimal control of coupled spin dynamics: design of nmr pulse sequences by gradient ascent algorithms.Journal of magnetic resonance, 172(2):296–305, 2005

    Navin Khaneja, Timo Reiss, Cindie Kehlet, Thomas Schulte-Herbrüggen, and Steffen J Glaser. Optimal control of coupled spin dynamics: design of nmr pulse sequences by gradient ascent algorithms.Journal of magnetic resonance, 172(2):296–305, 2005

    2005

  11. [11]

    Chopped random-basis quantum optimization.Physical Review A—Atomic, Molecular, and Optical Physics, 84(2):022326, 2011

    Tommaso Caneva, Tommaso Calarco, and Simone Montangero. Chopped random-basis quantum optimization.Physical Review A—Atomic, Molecular, and Optical Physics, 84(2):022326, 2011

    2011

  12. [12]

    Effectiveness of the krotov method in controlling open quantum systems.arXiv preprint arXiv:2208.03114, 2022

    Marllos E Fonseca, Felipe F Fanchini, Emanuel F de Lima, and Leonardo K Castelano. Effectiveness of the krotov method in controlling open quantum systems.arXiv preprint arXiv:2208.03114, 2022

    Pith/arXiv arXiv 2022

  13. [13]

    Tunable, flexible, and efficient optimization of control pulses for practical qubits.Physical review letters, 120(15):150401, 2018

    Shai Machnes, Elie Assémat, David Tannor, and Frank K Wilhelm. Tunable, flexible, and efficient optimization of control pulses for practical qubits.Physical review letters, 120(15):150401, 2018

    2018

  14. [14]

    Universal quantum control through deep reinforcement learning.npj Quantum Information, 5(1):33, 2019

    Murphy Yuezhen Niu, Sergio Boixo, Vadim N Smelyanskiy, and Hartmut Neven. Universal quantum control through deep reinforcement learning.npj Quantum Information, 5(1):33, 2019

    2019

  15. [15]

    Open and closed loop approaches for energy efficient quantum optimal control.Advanced Quantum Technologies, 8(10):2400690, 2025

    Sebastiaan Fauquenot, Aritra Sarkar, and Sebastian Feld. Open and closed loop approaches for energy efficient quantum optimal control.Advanced Quantum Technologies, 8(10):2400690, 2025

    2025

  16. [16]

    Time/space trade-offs for reversible computation.SIAM Journal on Computing, 18(4):766–776, 1989

    Charles H Bennett. Time/space trade-offs for reversible computation.SIAM Journal on Computing, 18(4):766–776, 1989

    1989

  17. [17]

    Reversible pebbling game for quantum memory management

    Giulia Meuli, Mathias Soeken, Martin Roetteler, Nikolaj Bjorner, and Giovanni De Micheli. Reversible pebbling game for quantum memory management. In2019 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 288–291. IEEE, 2019

    2019

  18. [18]

    The uncertainty relation between energy and time in non-relativistic quantum mechanics

    Leonid Mandelstam and IG Tamm. The uncertainty relation between energy and time in non-relativistic quantum mechanics. In Selected papers, pages 115–123. Springer, 1991

    1991

  19. [19]

    The maximum speed of dynamical evolution.Physica D: Nonlinear Phenomena, 120(1-2):188–195, 1998

    Norman Margolus and Lev B Levitin. The maximum speed of dynamical evolution.Physica D: Nonlinear Phenomena, 120(1-2):188–195, 1998

    1998

  20. [20]

    Generalized geometric quantum speed limits.Physical Review X, 6(2):021031, 2016

    Diego Paiva Pires, Marco Cianciaruso, Lucas C Céleri, Gerardo Adesso, and Diogo O Soares-Pinto. Generalized geometric quantum speed limits.Physical Review X, 6(2):021031, 2016

    2016

  21. [21]

    Quantum speed limits: from heisenberg’s uncertainty principle to optimal quantum control

    Sebastian Deffner and Steve Campbell. Quantum speed limits: from heisenberg’s uncertainty principle to optimal quantum control. Journal of Physics A: Mathematical and Theoretical, 50(45):453001, 2017

    2017

  22. [22]

    Springer, 2008

    Ming Li, Paul Vitányi, et al.An introduction to Kolmogorov complexity and its applications, volume 3. Springer, 2008

    2008

  23. [23]

    Symmetry principles in quantum systems theory.Journal of mathematical physics, 52(11), 2011

    Robert Zeier and Thomas Schulte-Herbrüggen. Symmetry principles in quantum systems theory.Journal of mathematical physics, 52(11), 2011

    2011

  24. [24]

    Classification of dynamical lie algebras for translation-invariant 2-local spin systems in one dimension.arXiv preprint arXiv:2309.05690, 2023

    Roeland Wiersema, Efekan Kökcü, Alexander F Kemper, and Bojko N Bakalov. Classification of dynamical lie algebras for translation-invariant 2-local spin systems in one dimension.arXiv preprint arXiv:2309.05690, 2023

    Pith/arXiv arXiv 2023

  25. [25]

    A universal operator growth hypothesis

    Daniel E Parker, Xiangyu Cao, Alexander Avdoshkin, Thomas Scaffidi, and Ehud Altman. A universal operator growth hypothesis. Physical Review X, 9(4):041017, 2019

    2019

  26. [26]

    Operator complexity: a journey to the edge of krylov space.Journal of High Energy Physics, 2021(6):1–24, 2021

    E Rabinovici, A Sánchez-Garrido, Ruth Shir, and J Sonner. Operator complexity: a journey to the edge of krylov space.Journal of High Energy Physics, 2021(6):1–24, 2021

    2021

  27. [27]

    Efficient solvability of hamiltonians and limits on the power of some quantum computational models.Physical review letters, 97(19):190501, 2006

    Rolando Somma, Howard Barnum, Gerardo Ortiz, and Emanuel Knill. Efficient solvability of hamiltonians and limits on the power of some quantum computational models.Physical review letters, 97(19):190501, 2006

    2006

  28. [28]

    Lie-algebraic classical simulations for quantum computing.Physical Review Research, 7(3):033266, 2025

    Matthew L Goh, Martin Larocca, Lukasz Cincio, Marco Cerezo, and Frédéric Sauvage. Lie-algebraic classical simulations for quantum computing.Physical Review Research, 7(3):033266, 2025

    2025

  29. [29]

    Optimalancilla-freeclifford+tapproximationofz-rotations.QuantumInf.Comput.,16(11&12):901– 953, 2016

    NeilJRossandPeterSelinger. Optimalancilla-freeclifford+tapproximationofz-rotations.QuantumInf.Comput.,16(11&12):901– 953, 2016

    2016

  30. [30]

    Eqisa: energy-efficient quantum instruction set architecture using sparse dictionary learning.arXiv preprint arXiv:2603.20646, 2026

    Sibasish Mishra, Aritra Sarkar, and Sebastian Feld. Eqisa: energy-efficient quantum instruction set architecture using sparse dictionary learning.arXiv preprint arXiv:2603.20646, 2026

    arXiv 2026

  31. [31]

    Mqt bench: Benchmarking software and design automation tools for quantum computing.Quantum, 7:1062, 2023

    Nils Quetschlich, Lukas Burgholzer, and Robert Wille. Mqt bench: Benchmarking software and design automation tools for quantum computing.Quantum, 7:1062, 2023

    2023

  32. [32]

    Universal sequential search problems.Problems of information transmission, 9(3):265–266, 1973

    Leonid A Levin. Universal sequential search problems.Problems of information transmission, 9(3):265–266, 1973

    1973

  33. [33]

    The speed prior: a new simplicity measure yielding near-optimal computable predictions

    Jürgen Schmidhuber. The speed prior: a new simplicity measure yielding near-optimal computable predictions. InInternational conference on computational learning theory, pages 216–228. Springer, 2002

    2002

  34. [34]

    A formal theory of inductive inference

    Ray J Solomonoff. A formal theory of inductive inference. part i.Information and control, 7(1):1–22, 1964. ⟨12⟩

    1964

  35. [35]

    Laws of information conservation (nongrowth) and aspects of the foundation of probability theory

    Leonid Anatolevich Levin. Laws of information conservation (nongrowth) and aspects of the foundation of probability theory. Problemy Peredachi Informatsii, 10(3):30–35, 1974

    1974

  36. [36]

    Visualizing quantum circuit probability: estimating quantum state complexity for quantum program synthesis.Entropy, 25(5):763, 2023

    Bao Gia Bach, Akash Kundu, Tamal Acharya, and Aritra Sarkar. Visualizing quantum circuit probability: estimating quantum state complexity for quantum program synthesis.Entropy, 25(5):763, 2023

    2023

  37. [37]

    Algorithmic thermodynamics.Mathematical Structures in Computer Science, 22(5):771–787, 2012

    John Baez and Mike Stay. Algorithmic thermodynamics.Mathematical Structures in Computer Science, 22(5):771–787, 2012

    2012

  38. [38]

    Foundations of algorithmic thermodynamics.Physical Review E, 111(1):014118, 2025

    Aram Ebtekar and Marcus Hutter. Foundations of algorithmic thermodynamics.Physical Review E, 111(1):014118, 2025

    2025

  39. [39]

    What is the lagrangian counting?International Journal of Theoretical Physics, 42(2):363–381, 2003

    Tommaso Toffoli. What is the lagrangian counting?International Journal of Theoretical Physics, 42(2):363–381, 2003

    2003

  40. [40]

    Action, quantum computation and the structure of the yang–mills lagrangian.Quantum Studies: Mathematics and Foundations, 1(3):173–185, 2014

    SA Selesnick. Action, quantum computation and the structure of the yang–mills lagrangian.Quantum Studies: Mathematics and Foundations, 1(3):173–185, 2014

    2014

  41. [41]

    na, 1988

    Charles H Bennett.Logical depth and physical complexity. na, 1988

    1988

  42. [42]

    Information measures, effective complexity, and total information.Complexity, 2(1):44–52, 1996

    Murray Gell-Mann and Seth Lloyd. Information measures, effective complexity, and total information.Complexity, 2(1):44–52, 1996

    1996

  43. [43]

    Effective complexity and its relation to logical depth.IEEE transactions on information theory, 56(9):4593–4607, 2010

    Nihat Ay, Markus Müller, and Arleta Szkola. Effective complexity and its relation to logical depth.IEEE transactions on information theory, 56(9):4593–4607, 2010

    2010

  44. [44]

    Complexity as thermodynamic depth.Annals of physics, 188(1):186–213, 1988

    Seth Lloyd and Heinz Pagels. Complexity as thermodynamic depth.Annals of physics, 188(1):186–213, 1988

    1988

  45. [45]

    Inferring statistical complexity.Physical review letters, 63(2):105, 1989

    James P Crutchfield and Karl Young. Inferring statistical complexity.Physical review letters, 63(2):105, 1989

    1989

  46. [46]

    A theory of universal artificial intelligence based on algorithmic complexity.arXiv preprint cs/0004001, 2000

    Marcus Hutter. A theory of universal artificial intelligence based on algorithmic complexity.arXiv preprint cs/0004001, 2000

    Pith/arXiv arXiv 2000

  47. [47]

    Qksa: Quantum knowledge seeking agent

    Aritra Sarkar, Zaid Al-Ars, and Koen Bertels. Qksa: Quantum knowledge seeking agent. InInternational Conference on Artificial General Intelligence, pages 384–393. Springer, 2022

    2022

  48. [48]

    Quantum aixi: Universal intelligence via quantum information

    Elija Perrier. Quantum aixi: Universal intelligence via quantum information. InInternational Conference on Artificial General Intelligence, pages 58–70. Springer, 2025

    2025

  49. [49]

    The tao of agency: Autotelic ai, embedded agency and dissolution of the self.arXiv preprint arXiv:2606.19924, 2026

    Aritra Sarkar. The tao of agency: Autotelic ai, embedded agency and dissolution of the self.arXiv preprint arXiv:2606.19924, 2026

    Pith/arXiv arXiv 2026

  50. [50]

    JennyZhang,ShengranHu,CongLu,RobertLange,andJeffClune.Darwingodelmachine: Open-endedevolutionofself-improving agents.arXiv preprint arXiv:2505.22954, 2025

    Pith/arXiv arXiv 2025

  51. [51]

    Hyperagents.arXiv preprint arXiv:2603.19461, 2026

    Jenny Zhang, Bingchen Zhao, Wannan Yang, Jakob Foerster, Jeff Clune, Minqi Jiang, Sam Devlin, and Tatiana Shavrina. Hyperagents.arXiv preprint arXiv:2603.19461, 2026

    arXiv 2026

  52. [52]

    Gödel machines: Fully self-referential optimal universal self-improvers

    Jürgen Schmidhuber. Gödel machines: Fully self-referential optimal universal self-improvers. InArtificial general intelligence, pages 199–226. Springer, 2007

    2007

  53. [53]

    bzip2 and libbzip2.avaliable at http://www

    Julian Seward. bzip2 and libbzip2.avaliable at http://www. bzip. org, pages 8–18, 1996

    1996

  54. [54]

    Pybdm: Python interface to the block decomposition method (0.1

    S Talaga and K Tsampourakis. Pybdm: Python interface to the block decomposition method (0.1. 0). software, 2024

    2024

  55. [55]

    Calculating kolmogorov complexity from the output frequency distributions of small turing machines.PloS one, 9(5):e96223, 2014

    Fernando Soler-Toscano, Hector Zenil, Jean-Paul Delahaye, and Nicolas Gauvrit. Calculating kolmogorov complexity from the output frequency distributions of small turing machines.PloS one, 9(5):e96223, 2014

    2014

  56. [56]

    Yaqq: yet another quantum quantizer design space exploration of quantum gate sets using novelty search.New Journal of Physics, 28(4):044504, 2026

    Aritra Sarkar, Akash Kundu, Matthew Steinberg, Sibasish Mishra, Sebastiaan Fauquenot, Tamal Acharya, Jarosław A Miszczak, and Sebastian Feld. Yaqq: yet another quantum quantizer design space exploration of quantum gate sets using novelty search.New Journal of Physics, 28(4):044504, 2026

    2026

  57. [57]

    Super-golden-gates for pu (2).Advances in Mathematics, 327:869–901, 2018

    Ori Parzanchevski and Peter Sarnak. Super-golden-gates for pu (2).Advances in Mathematics, 327:869–901, 2018

    2018

  58. [58]

    Discovering quantum circuit components with program synthesis.Machine Learning: Science and Technology, 5(2):025029, 2024

    Leopoldo Sarra, Kevin Ellis, and Florian Marquardt. Discovering quantum circuit components with program synthesis.Machine Learning: Science and Technology, 5(2):025029, 2024

    2024

  59. [59]

    Mlir: A compiler infrastructure for the end of moore’s law.arXiv preprint arXiv:2002.11054, 2020

    Chris Lattner, Mehdi Amini, Uday Bondhugula, Albert Cohen, Andy Davis, Jacques Pienaar, River Riddle, Tatiana Shpeisman, Nicolas Vasilache, and Oleksandr Zinenko. Mlir: A compiler infrastructure for the end of moore’s law.arXiv preprint arXiv:2002.11054, 2020

    Pith/arXiv arXiv 2002

  60. [60]

    Qssa: an ssa-based ir for quantum computing

    Anurudh Peduri, Siddharth Bhat, and Tobias Grosser. Qssa: an ssa-based ir for quantum computing. InProceedings of the 31st ACM SIGPLAN International Conference on Compiler Construction, pages 2–14, 2022

    2022

  61. [61]

    The structure and performance of efficient interpreters.Journal of Instruction-Level Parallelism, 5:1–25, 2003

    M Anton Ertl and David Gregg. The structure and performance of efficient interpreters.Journal of Instruction-Level Parallelism, 5:1–25, 2003

    2003

  62. [62]

    Deqompile: quantum circuit decompilation using genetic programming for explainable quantum architecture search.arXiv preprint arXiv:2504.08310, 2025

    Shubing Xie, Aritra Sarkar, and Sebastian Feld. Deqompile: quantum circuit decompilation using genetic programming for explainable quantum architecture search.arXiv preprint arXiv:2504.08310, 2025

    Pith/arXiv arXiv 2025

  63. [63]

    Compression and explanation using hierarchical grammars.The Computer Journal, 40(2_and_3):103–116, 1997

    Craig G Nevill-Manning and Ian H Witten. Compression and explanation using hierarchical grammars.The Computer Journal, 40(2_and_3):103–116, 1997. ⟨13⟩

    1997