Pith. sign in

REVIEW 4 major objections 5 minor 65 references

A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization

T0 review · 4 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read This paper argues that random sampling of a compressible objective, followed by thresholding, sketching generalized moments, and greedy matching-pursuit decoding, finds the global optimum with far fewer than 2^N queries.

desk verdict Genuinely novel repurposing of compressive sensing for black-box optimization, but the final uniqueness proof separates the wrong moments and the numerics are too thin. read the letter →

arxiv 2510.24755 v2 pith:VIQU7AW6 submitted 2025-10-20 math.OC quant-ph

Baptiste Chevalier , Shimpei Yamaguchi , Wojciech Roga , Masahiro Takeoka This is my paper · ORCID
classification math.OCquant-ph MSC 90C2768W20
keywords compressivesensingcombinatorialoptimizationMonteCarlomethodmatchingpursuitgeneralizedmomentsblack-boxsparserulefunctionsdualannealing
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper tries to establish that many hard black-box combinatorial problems—those whose objective is 'compressible' because it is determined by a small set of substring rules—can be solved without exploring the 2^N search space. Its method samples the objective at random points, drops low values, and uses the sampled values to estimate generalized moments; a greedy compressive-sensing decoder then picks the bitstring whose local correlation structure best matches those moments. The claim is that this recovers the global optimum, or a near neighbor of it, from a few hundred queries even when the optimum was never sampled, and the numerical comparison with dual annealing at equal query budgets is the evidence offered. The theoretical justification rests on moment concentration, thresholding, and a separation argument for the transforms of distinct rules, with the caveat that the key separation step assumes the sketching map preserves distances.

What carries the argument

The load-bearing objects are the rule transform F_N and the sketch-then-decode pipeline. F_N maps a k-bit rule r to the 2^N-dimensional vector whose x-th entry counts how many times r appears as a substring of x; the objective f_R is then the weighted sum of the F_N(r). A sketching map Φ compresses the thresholded sample into M generalized moments, and the decoding step—matching pursuit rather than ℓ1 minimization—greedily selects the bitstring whose adjacent-bit correlations have the largest inner product with those moments. The separation lemmas (Lemma 1 injectivity, Lemma 2 exponential growth of ∥F_N(a)−F_N(b)∥2) are what allow distinct rules to become distinguishable in moment space; The

What would settle it

Enumerate all distinct 4-, 5-, and 6-bit rules from the numerical section, compute ΦF_N(a)−ΦF_N(b) for the quadruplet, quintuplet, and random binary sketches at N=12, and compare the smallest such distance with the concentration-ball diameter D from Theorem 3; if any pair of distinct rules falls within D, the uniqueness argument in Section VI.C cannot hold for that sketch, and the question becomes whether the algorithm still recovers optima by a different mechanism.

Watch

Extended reading notes

Core claim

The central claim is that combinatorial optimization over bitstrings becomes tractable when the objective function is compressible: its values are fixed by a short list of substring rules (a substring r with reward ω contributes ω for every occurrence of r in the input). The proposed Monte-Carlo Compressive Optimization algorithm draws n uniform samples of f, keeps only values above a threshold t, applies a sketching map Φ to estimate generalized moments of the normalized reward distribution, and then runs a matching-pursuit decoder to produce a sparse surrogate distribution; the largest entry of that surrogate is the estimate of the optimum. The paper argues that solving this moment-recover

Load-bearing premise

The load-bearing premise is that the sketching map used to compress samples nearly preserves distances between the transforms of distinct rules (the Restricted Isometry Property), and the paper does not verify this property for any of the three sketches it actually tests.

Editorial extensions

If this is right

  • On the tested class of compressible functions (N=12, rules of length 4–6), the algorithm matches or beats dual annealing at the same number of objective calls, and finds the exact optimum in a majority of runs with the structured sketches.
  • Because the method only needs uniform random samples of the objective, it applies to black-box oracles where the optimum is never sampled, and where gradient or convexity information is unavailable.
  • Choosing a sketch with more structure trades memory and computation for accuracy; quadruplet and quintuplet sketches outperform a random binary matrix, consistent with the paper's variance-reduction argument.
  • The F_N separation theorems imply that, as N grows, distinct rules become increasingly easy to tell apart in moment space, so the distinguishability bottleneck shifts to the sketching map and the sample size.
  • The preference for matching pursuit over ℓ1 recovery is justified as an anti-overfitting choice: greedy decoding tracks global features of the distribution, which is exactly what is needed to locate the maximum line.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the same pipeline should, in principle, handle objectives built from overlapping or long-range rules, since the F_N separation argument is rule-agnostic; a direct extension would test rule lengths beyond 6 and overlapping rules at larger N.
  • Editorial inference: the unverified Restricted Isometry Property is the main gap between the paper's uniqueness narrative and its numerical demonstrations; a coherence calculation for the three sketch families against the tested rule set would settle whether the separation mechanism is actually active.
  • Editorial inference: if the method is robust, the moment-based viewpoint suggests a query-complexity tradeoff for learning low-degree Boolean functions, where the threshold parameter t controls a bias-variance split between distribution-level and sample-level features—an analysis the paper leaves open.
  • Editorial inference: the paper's quantum discussion suggests a concrete hybrid: structure Φ so the matching-pursuit inner loop becomes a spin-glass search; testing that search classically would benchmark whether a quantum device could help.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper proposes a Monte-Carlo Compressive Optimization algorithm for combinatorial optimization over binary strings of length N. It assumes the objective function is determined by a small set of unknown substring rules with additive rewards. The algorithm samples the objective uniformly, applies a hard threshold to low values, computes a low-dimensional sketch (via random binary, quadruplet, or quintuplet moment maps), and then uses matching pursuit to decode a candidate global optimum. The authors report numerical comparisons against dual annealing on N=12 instances, claiming competitive or better performance at equal query budgets, and provide a theoretical discussion aimed at justifying stability, concentration, and uniqueness of recovery. An open-source implementation is provided.

Significance. If the theoretical claims were established, the paper would introduce a genuinely new approach to black-box combinatorial optimization: exploiting compressibility of the objective without knowing the underlying rules, with query counts potentially far below 2^N. The numerical results on small instances, together with the open-source code, are a useful empirical contribution. However, the current theoretical justification contains substantial gaps—most importantly, the uniqueness argument in Section VI.C compares unthresholded moments while the algorithm uses thresholded moments, and the RIP assumption needed for Theorem 5 is not verified for any sketch actually tested. The paper itself states in Section V that rigorous bounds are lacking. Thus the claimed theoretical foundation is not yet delivered.

major comments (4)
  1. [Section VI.C, Eqs. (20)-(21)] The final uniqueness argument conflates two different distributions. Theorem 5 lower-bounds ||Phi(F_N(a))-Phi(F_N(b))|| for unthresholded rule embeddings, but Algorithm 1 forms its sketch from thresholded samples, Phi(T_t S_I f_R), whose expectation is y(t)=E[Phi(T_t f_R(x))]. The Monte-Carlo estimates concentrate around y_a(t), y_b(t), not around y_a, y_b. No bound is given on ||y(t)-y||. Thresholding removes low-reward entries, which are exactly where two rules' occurrence patterns differ, so the thresholded centers can move together. Theorem 3 makes D(t) arbitrarily small by increasing t, but that concerns radii around the thresholded centers, not their separation. The disjoint-ball conclusion is therefore not established.
  2. [Section VI.B, Theorem 5 and Section IV] Theorem 5 assumes the sketching map Phi satisfies the Restricted Isometry Property on the rule transforms F_N(a). The three sketches actually tested in Section IV—quadruplets, quintuplets, and random binary matrices—are never shown to satisfy RIP or any coherence substitute. Without this, the separation result does not apply to the numerical experiments. The paper should either prove RIP/coherence for these structured measurements, or use a measurement ensemble with a proven RIP guarantee and state that the numerical section uses it.
  3. [Appendix C.2, proof of Theorem 2] The proof that thresholding reduces variance assumes f_R can be approximated by an exponential law after reordering the function values. This is a strong, unverified distributional assumption; the theorem statement does not include it, and no approximation error is controlled. Without this assumption, the existence of t with sigma^{(t)}^2 <= sigma^2 is not proven—thresholding can increase variance for general distributions. Since Theorem 3 and the concentration-with-thresholding claims rely on Theorem 2, this gap affects the core theoretical narrative.
  4. [Section VI.A, Theorem 3] The statement that D(t) becomes arbitrarily small as t increases is not justified. Theorem 2 only establishes existence of some t that reduces variance, not monotonicity in t, and sigma^{(t)} can initially increase. Moreover, epsilon^{(t)} is defined via sigma^{(t)}/sqrt(n); even if radii shrink, the centers y_a(t), y_b(t) may shift (see the first major comment). Thus the conclusion of disjoint balls with high probability is vacuous without a bound on the thresholding bias.
minor comments (5)
  1. [Section III, Algorithm 1] Typo: 'sketch fucntion' should be 'sketch function'. Also, the notation T_t S f_R is used before being formally defined; the distinction between applying the threshold to the sample versus to the full function is clarified later but could appear earlier.
  2. [Section III, Problem II] The definition of Problem II writes 'arg max ΦT ΦT S f_R' which is dimensionally unclear. It likely means the argument maximizing the inner product of the sketch row with the thresholded sample, but the transpose notation and the role of T_t should be made explicit.
  3. [Section V, Proposition 1] The subscript notation φ_{i,i+1}_x in Proposition 1 is inconsistent with the earlier definition using x1,x2. This makes the statement harder to follow, especially the thresholded version in part (iii).
  4. [Appendix D.2] At the end of the proof of Lemma 2, the text says 'we get Theorem2' but should say 'Lemma 2.'
  5. [Throughout] There are several grammatical issues ('evidences', 'subsings', 'recursivity') and inconsistent references (e.g., Figure 3 is referenced but not clearly introduced). A careful proofread is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the algorithm's estimates are not fitted to the optimum and the cited self-work is not load-bearing.

full rationale

The derivation chain is self-contained in the sense relevant to circularity. The objective f_R is defined by rules and the transform F_N, and the algorithm estimates moments from random samples S_I f_R, thresholds them, sketches them, and decodes with matching pursuit. No parameter is fitted to the target optimum x* in a way that is then renamed as a prediction; the threshold t and sketch Φ are chosen before decoding and the paper explicitly disclaims rigorous success bounds ("we do not have the rigorous theoretical bounds on the probability with which Algorithm 1 approaches the correct solution"). Proposition 1 is a direct calculation for single-rule expected moments, and Theorems 1-5 establish concentration and separation of rule images under an explicit RIP hypothesis. The self-citations [22,23] are used only as examples of structured measurement functions and for the quantum discussion in Section VII, not as premises of the main uniqueness or concentration arguments, so they are not load-bearing. The final uniqueness argument in Section VI.C does contain a genuine proof gap: it places thresholded Monte-Carlo estimates in balls around "moments y_a and y_b" while Theorem 5 separates the unthresholded images Φ(F_N(a)) and Φ(F_N(b)), and the bias between thresholded and unthresholded expectations is never bounded. This is a correctness/rigor concern, not an equivalence-by-construction or fitted-input-called-prediction circularity. The RIP assumption for the tested sketches is also unproven, but again that is a missing hypothesis check rather than a circular reduction. Overall, no step of the derivation reduces to its own inputs by definition or by self-citation, so the circularity score is 0.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

No new physical entities are postulated; 'rule' and F_N are formal mathematical constructions. The central claim rests mainly on the compressibility domain assumption and on unproven properties (greedy recovery, RIP, threshold preservation) rather than on new ontology.

free parameters (2)
  • Threshold parameter t = not specified
    Algorithm 1 requires a hard-thresholding parameter t; the paper says it can be tuned to available computational resources, but no value or selection rule is reported in the numerical section. Theorem 2 only proves existence of a suitable t under an exponential approximation.
  • Sketch dimension M (number of moment rows) = not specified
    The random binary and structured sketches have a row count M that is not reported; M controls the overfitting/generalization trade-off in the greedy decoder and is a heuristic parameter.
assumptions (5)
  • domain assumption The objective function is compressible: f_R is fully determined by a few substring rules (Section II)
    The entire algorithm and justification apply only to functions with this structure; real-world black-box functions may not be compressible.
  • ad hoc to paper Greedy matching-pursuit decoding of sample moments returns the maximum line of the underlying distribution rather than the sample's idiosyncrasies (Section III/V)
    The authors state that greedy methods 'focus on finding the one line that matches the best all constraints and this line often matches with the maximum line'—an unproved intuition central to Algorithm 1.
  • domain assumption Thresholding preserves the location of the global maximum (Section VI.A)
    The concentration improvement via thresholding is only valid if the thresholded moment remains close to the true moment; too aggressive a threshold can delete the optimum line.
  • ad hoc to paper f_R can be approximated by an exponential law after reordering, used in the proof of Theorem 2 (Appendix C.2)
    The variance-reduction theorem is proved only under this distributional approximation plus an intermediate-value argument; no evidence is given that substring-rule functions follow this law.
  • domain assumption The sketch Φ satisfies the Restricted Isometry Property for the vectors F_N(a) (Theorem 5)
    Not verified for quadruplets, quintuplets, or random binary sketches; without RIP or a coherence bound the rule-separation result does not transfer to the measured moments.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization." pith.science (2026). https://pith.science/paper/VIQU7AW6

@misc{pith2026251024755,
  author       = {Pith},
  title        = {Pith review of: A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VIQU7AW6}},
  note         = {Machine review of arXiv:2510.24755}
}
read the original abstract

In this paper, we present a Monte-Carlo Compressive Optimization algorithm, a new method to tackle combinatorial optimization problems, including Black-Box or complicated objective functions. The method relies on random queries to the objective function in order to estimate generalized moments. Next, a greedy algorithm from compressive sensing is repurposed to find the global optimum when not overfitting to the samples. We provide numerical results giving evidence that our method is competitive by comparing it with dual annealing. Moreover, we give theoretical justification for the success of the algorithm and analyze its properties. The practicality of our algorithm is enhanced by the ability to tune the heuristic parameters to the available computational resources. An end-to-end open-source implementation is available to use our method.

Figures

Figures reproduced from arXiv: 2510.24755 by the authors.

Figure 4
Figure 4. First observation is that all three sketching [PITH_FULL_IMAGE:figures/full_fig_p004_4.png] view at source ↗
Figure 1
Figure 1. FIG. 1: Distribution of the distance between estimate solutions [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2: Distribution of the Hamming distance between estimate solutions [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figures from the paper (2 more)
Figure 3
Figure 3. Figure 3: FIG. 3: Example of [PITH_FULL_IMAGE:figures/full_fig_p007_3.png]
Figure 4
Figure 4. Figure 4: FIG. 4: Estimate distance to the minimum when the [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

65 extracted references · 7 linked inside Pith

  1. [1]

    To do so: First, draw a sampleIofnindices from the uniform dis- tribution

    Compute a sample offcalledSf. To do so: First, draw a sampleIofnindices from the uniform dis- tribution. Then apply the sampling operatorS I defined asS I :x7→xδ x,y∈I tof

  2. [2]

    Apply ahard thresholdingoperatorT t such that inT tSfall valuesSf(x) lower than a giventare removed from the sample

  3. [3]

    We callythe sketch vector and it contains an em- pirical estimation ofgeneralized momentsof the dis- tributionπ

    Apply asketching map(also known as a measure- ment map or a feature map) Φ to gety= Φ(T tSf). We callythe sketch vector and it contains an em- pirical estimation ofgeneralized momentsof the dis- tributionπ

  4. [4]

    The decoding procedure is taken from com- pressive sensinggreedy methods(Matching pur- suit, Orthogonal Matching Pursuit

    Apply a decoding procedure ∆ toyand get ˜π= ∆(y). The decoding procedure is taken from com- pressive sensinggreedy methods(Matching pur- suit, Orthogonal Matching Pursuit . . . )

  5. [5]

    The Monte-Carlo method [17] can be used to approx- imate generalized moments similar to the one from [16]

    The largest line of ˜πis used as the maximum esti- mate. The Monte-Carlo method [17] can be used to approx- imate generalized moments similar to the one from [16]. This is a well known result from the probabilistic compu- tation theory (or ergodic theory), about a large number Mof samples sampled independently from a probability distributionπ, lim M→∞ 1 M...

  6. [6]

    Kadowaki and H

    T. Kadowaki and H. Nishimori, Physical Review E58, 5355 (1998)

    1998

  7. [7]

    Robbins and S

    H. Robbins and S. Monro, The Annals of Mathematical Statistics22, 400 (1951), publisher: Institute of Mathe- matical Statistics

    1951

  8. [8]

    J. A. Nelder and R. Mead, The Com- puter Journal7, 308 (1965), eprint: https://academic.oup.com/comjnl/article- pdf/7/4/308/1013182/7-4-308.pdf

    1965

Show all 65 references
  1. [9]

    M. J. D. Powell, inAdvances in Optimization and Nu- merical Analysis, edited by S. Gomez and J.-P. Hennart (Springer Netherlands, Dordrecht, 1994) pp. 51–67

    1994

  2. [10]

    Lucas, Frontiers in Physics2(2014), 10.3389/fphy.2014.00005, arXiv:1302.5843 [cond-mat]

    A. Lucas, Frontiers in Physics2(2014), 10.3389/fphy.2014.00005, arXiv:1302.5843 [cond-mat]

    2014

  3. [11]

    Kirkpatrick, C

    S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Science 220, 671 (1983)

    1983

  4. [12]

    Candes, J

    E. Candes, J. Romberg, and T. Tao, IEEE Transactions on Information Theory52, 489 (2006)

    2006

  5. [13]

    Quantum annealing: An introduction and new developments,

    M. Ohzeki and H. Nishimori, “Quantum annealing: An introduction and new developments,” (2010), arXiv:1006.1696 [cond-mat]

    2010 arXiv

  6. [14]

    Bellman, Bulletin of the American Mathematical So- ciety60, 503 (1954)

    R. Bellman, Bulletin of the American Mathematical So- ciety60, 503 (1954)

    1954

  7. [15]

    Barahona, Journal of Physics A: Mathematical and General15, 3241 (1982)

    F. Barahona, Journal of Physics A: Mathematical and General15, 3241 (1982)

    1982

  8. [16]

    as well as on Monte-Carlo methods [17, 18]. Compressive sensing is a well established field which al- lows for recovering a high dimensional signal from small number of linear measurements given that one knows a basis in which the signal has a sparse representation. The recove...

    2025 arXiv

  9. [17]

    Schuch and J

    N. Schuch and J. I. Cirac, Phys. Rev. A82, 012314 (2010)

    2010

  10. [18]

    Delahaye, S

    D. Delahaye, S. Chaimatanan, and M. Mongeau, in Handbook of Metaheuristics, edited by M. Gendreau and J.-Y. Potvin (Springer International Publishing, Cham,

  11. [19]

    Donoho, IEEE Transactions on Information Theory 52, 1289 (2006)

    D. Donoho, IEEE Transactions on Information Theory 52, 1289 (2006)

    2006

  12. [20]

    Baraniuk, M

    R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, Constructive Approximation28, 253 (2008)

    2008

  13. [21]

    Foucart and H

    S. Foucart and H. Rauhut, inA Mathematical Introduc- tion to Compressive Sensing, edited by S. Foucart and H. Rauhut (Springer, New York, NY, 2013) pp. 61–75

    2013

  14. [22]

    Compressive Statistical Learning with Random Feature Moments,

    R. Gribonval, G. Blanchard, N. Keriven, and Y. Traon- milin, “Compressive Statistical Learning with Random Feature Moments,” (2021), arXiv:1706.07180 [stat]

    2021 arXiv

  15. [23]

    Metropolis and S

    N. Metropolis and S. Ulam, Journal of the American Sta- tistical Association44, 335 (1949), publisher: [American Statistical Association, Taylor & Francis, Ltd.]

    1949

  16. [24]

    Metropolis, A

    N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, The Journal of Chemical Physics21, 1087 (1953)

    1953

  17. [25]

    Xiang, D

    Y. Xiang, D. Y. Sun, W. Fan, and X. G. Gong, Physics Letters A233, 216 (1997)

    1997

  18. [26]

    Tsallis, Journal of Statistical Physics52, 479 (1988)

    C. Tsallis, Journal of Statistical Physics52, 479 (1988)

    1988

  19. [27]

    Tsallis and D

    C. Tsallis and D. A. Stariolo, Physica A: Statistical Me- chanics and its Applications233, 395 (1996). 12

    1996

  20. [28]

    K. V. Jacob, E. Kaur, W. Roga, and M. Takeoka, Phys. Rev. A102, 032403 (2020)

    2020

  21. [29]

    Chevalier, W

    B. Chevalier, W. Roga, and M. Takeoka, Physical Re- view A110, 062410 (2024), publisher: American Physi- cal Society

    2024

  22. [30]

    W. K. Hastings, Biometrika57, 97 (1970)

    1970

  23. [31]

    C. J. C. H. Watkins and P. Dayan, Machine Learning8, 279 (1992)

    1992

  24. [32]

    V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wier- stra, S. Legg, and D. Hassabis, Nature518, 529 (2015), publisher...

    2015

  25. [33]

    NP-complete Problems and Physical Re- ality,

    S. Aaronson, “NP-complete Problems and Physical Re- ality,” (2005), arXiv:quant-ph/0502072

    2005 arXiv

  26. [34]

    Quantum Computation by Adiabatic Evolution,

    E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, “Quantum Computation by Adiabatic Evolution,” (2000), arXiv:quant-ph/0001106

    2000 arXiv

  27. [35]

    A Quan- tum Approximate Optimization Algorithm,

    E. Farhi, J. Goldstone, and S. Gutmann, “A Quan- tum Approximate Optimization Algorithm,” (2014), arXiv:1411.4028 [quant-ph]

    2014 arXiv

  28. [36]

    Zhou, S.-T

    L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Physical Review X10, 021067 (2020)

    2020

  29. [37]

    Park and N

    C.-Y. Park and N. Killoran, Quantum8, 1239 (2024), publisher: Verein zur F¨ orderung des Open Access Pub- lizierens in den Quantenwissenschaften

    2024

  30. [38]

    McArdle, T

    S. McArdle, T. Jones, S. Endo, Y. Li, S. C. Benjamin, and X. Yuan, npj Quantum Information5, 1 (2019)

    2019

  31. [39]

    Dissipative ground state preparation and the Dissipative Quantum Eigensolver,

    T. S. Cubitt, “Dissipative ground state preparation and the Dissipative Quantum Eigensolver,” (2023), arXiv:2303.11962 [quant-ph]

    2023 arXiv

  32. [40]

    Rapid quantum ground state preparation via dissipative dynamics,

    Y. Zhan, Z. Ding, J. Huhn, J. Gray, J. Preskill, G. K.-L. Chan, and L. Lin, “Rapid quantum ground state preparation via dissipative dynamics,” (2025), arXiv:2503.15827 [quant-ph]. Appendix A: Proof of Proposition 1—Larger momemnts of substrings of the rules Proof.Formally, φi,...

    2025

  33. [41]

    Count the string that contains a single 001

  34. [42]

    The probability in that string to find 001 after 00 is given by 1 L

    Belong them estimate the number of that containsLtimes 00 as a substring. The probability in that string to find 001 after 00 is given by 1 L

  35. [43]

    Compute the expectated probability for allL 14

  36. [44]

    We want to count all the strings of a given lengthNwhich contains at least one ‘001‘ substring

    Counting the string that contains a single001 We start by counting the string that contains at least one 001 as a substring. We want to count all the strings of a given lengthNwhich contains at least one ‘001‘ substring. We defineE N = {s—shas at least one substring equals 001...

  37. [45]

    Because form∈S N , ifmend by ‘00‘ the othersN−2 bits are free and should contains ‘001‘ a single time

    For all stringm∈S N we can build a new stringm ′ =m· ∗Ifmdoesn’t end by ‘00‘ thenm ′ contains a single time ‘001‘ becausemitself contains a single time ‘001‘. Because form∈S N , ifmend by ‘00‘ the othersN−2 bits are free and should contains ‘001‘ a single time. The number of s...

  38. [46]

    Because the last 3 bits are fixed to ‘001‘ the remainingN−2 bits are free and should not contain any ‘001‘

    We need to add all the other strings that end by ‘001‘ and did not contains any ‘001‘ before. Because the last 3 bits are fixed to ‘001‘ the remainingN−2 bits are free and should not contain any ‘001‘ . Thus there are #(string of length N-2)−e N−2 such strings (wheree N is def...

  39. [47]

    The goal is to compute the its cardinalityz L = #ZL

    Counting the number string with exactlyL00 in a string that contains a single 001 We defineZ L ={s∈S N |sas exactlyLsubstrings equal 00}. The goal is to compute the its cardinalityz L = #ZL. Claim 5.There is an explicit expression forz L given by zL = N−2X k=1 fk−L+1fN−k + LX ...

  40. [48]

    19 Case 1: Assume we have a zero in positionk−1 so we have two 00 substrings. s=. . . . . .| {z } k−2 00 ↑ k

  41. [49]

    Case 2: Assume we have two zeros starting in positionN−1 so we have two 00 substrings in total

    | {z } N−(k+2) The strings∈Z 2 is of the forms=w 1 ·0001·w 2 where: •w 1 ∈A ∗ k−2 •w 2 ∈A N−(k+2) So the number of all such stringssisa ∗ k−2aN−k−2 =f k−1fN−k . Case 2: Assume we have two zeros starting in positionN−1 so we have two 00 substrings in total. s=. . . . . .| {z } ...

  42. [50]

    | {z } N−2−(k+2) 00 The strings∈Z 2 is of the forms=w 1 ·001·w 2 ·00 where: •w 1 ∈A ∗ k−1 •w 2 ∈A ∗ N−k−4 So the number of all such stringssisa ∗ k−1a∗ N−k−4 =f k−1fN−k−3 . There are no other cases becausescontains a single 001 so if any other places contains 00, following by ...

  43. [51]

    Case 1: Assume we haveL−1 zeros in positionsk−Ltok−1 so we have exactlyLsubstrings equals 00

    We now reproduce the same two previous case and add intermediates ones. Case 1: Assume we haveL−1 zeros in positionsk−Ltok−1 so we have exactlyLsubstrings equals 00. s=. . .|{z} k−L

  44. [52]

    0| {z } L−1 001·w 2 where: •w 1 ∈A ∗ k−L •w 2 ∈A N−(k+2) So the number of all such stringssisa ∗ k−LaN−(k+2) =f k−L+1fN−k

    | {z } N−(k+2) The strings∈Z L is of the forms=w 1 ·0. . .0| {z } L−1 001·w 2 where: •w 1 ∈A ∗ k−L •w 2 ∈A N−(k+2) So the number of all such stringssisa ∗ k−LaN−(k+2) =f k−L+1fN−k . Case 2: Assume we haveLzeros starting in positionN−L+ 1 so we haveLsubstrings equals 00 in tota...

  45. [53]

    0| {z } L where: 20 •w 1 ∈A ∗ k−1 •w 2 ∈A ∗ N−L−k−2 So the number of all such stringssisa ∗ k−1a∗ N−L−k−2 =f kfN−L−k−1

    0| {z } L The strings∈Z L is of the forms=w 1 ·001·w 2 ·0. . .0| {z } L where: 20 •w 1 ∈A ∗ k−1 •w 2 ∈A ∗ N−L−k−2 So the number of all such stringssisa ∗ k−1a∗ N−L−k−2 =f kfN−L−k−1 . Intermediates Cases: We can go incrementally from case 1 to case 2 by removing one zero at the...

  46. [54]

    |{z} k−L

    | {z } N−(k+2) . . .|{z} k−L

  47. [55]

    |{z} k−L

    | {z } N−2−(k+2) 00 . . .|{z} k−L

  48. [56]

    | {z } k−L 00 ↑ k

    | {z } N−3−(k+2) 000 ... . . . . . .| {z } k−L 00 ↑ k

  49. [57]

    | {z } k−1 0 ↑ k

    0| {z } L−1 . . . . . .| {z } k−1 0 ↑ k

  50. [58]

    0| {z } L we see the pattern being revealed, each time we remove one zero before 001 and add one more at the end. This can be written as the next expression: fk−L+1fN−k + LX ℓ=2 fk−L+ℓfN−ℓ−k−1 (B12) where the first term in front reduces to Case 1 (it is a bit different to othe...

  51. [59]

    Computing the probability Theorem 6.The probabilityP N for the rule 001 of sizem= 3 to realize after matchingm−1 = 2 bits 00 given that the strings of interest all contains exactlyq= 1, a single times the rule is given by PN = N−1X L=1 1 L zL SN (B13) where the expression ofS ...

  52. [60]

    Proof of Theorem 1 Proof.[Moment concentration] First, one uses the Chebyshev’s inequality (the distance of a sample to its mean) and gets P(|ˆyn − ⟨ˆyn⟩| ≥k˜σ)≤1 k2 wherek∈Nand ˜σ 2 = Var(ˆyn). Next ˜σandσcan be related as follows: Var(ˆyn) = Var[1 n X i Φ(fR(x(i)))] = 1 n2 V...

  53. [61]

    Proof of Theorem 3 Lemma 4.[Concentration Bound with Thresholding] Letσ (t)2 = Var[Φ(TtfR(x))] be the variance of the thresholded function. The following expression holds: σ(t)2 =p(t)σ 2 1(t) +µ 2 1(t)(1−p(t)p(t) (C1) wherep(t) is the probability to sample from the non-zero re...

  54. [62]

    Proof of Lemma 1 The following claim is prerequisite to show Lemma 1. Claim 6. a̸= 0 (k) =⇒F N (a)[ia] = 1 (D1) Proof.The proof is by contradiction. a=a 1 · · ·ak matches withi a = 0(N−k) a1 · · ·ak at the lastkbits. If we assumeF N (a)[ia]>1, then,amatches with ia at somewher...

  55. [63]

    ∥FN (a)−F N (b)∥2 2 =FN (a)·F N (a) +F N (b)·F N (b)−2F N (a)·F N (b) Thus, we will analyzeF N (a)·F N (b)

    Proof of Lemma 2 Proof. ∥FN (a)−F N (b)∥2 2 =FN (a)·F N (a) +F N (b)·F N (b)−2F N (a)·F N (b) Thus, we will analyzeF N (a)·F N (b). From Fk+l(a) = l+1X i=1 1⊗(i−1) 2 ⊗ |a⟩ ⊗1⊗(l+1−i) 2 , the inner product becomes Fk+l(a)·F k+l(b) = l+1X i=1 1⊗(i−1) 2 ⊗ |a⟩ ⊗1⊗(l+1−i) 2 T l+1X ...

  56. [64]

    ConcatenateF N (a) andF N (a),

  57. [65]

    The 2N+1 length vector indicating the position of (N+ 1)-bit strings which start fromacan be written asa⊗1 2N−k+1 , since there are 2 N+1−k strings like that

    Add 1 to the elements of which indexes start fromk-bit stringa. The 2N+1 length vector indicating the position of (N+ 1)-bit strings which start fromacan be written asa⊗1 2N−k+1 , since there are 2 N+1−k strings like that. Thus, the equation in Claim 7 holds. Lemma 5.[ℓ 1-Norm...

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.