acceptodds
Under review as a conference paper at ICLR 2027

One Qubit, Two Classical States: A Certified Memory Gap

Abstract

A quantum model can beat every classical model we train without establishing a memory advantage: a better classical model may remain undiscovered. We develop certificates that rule out this possibility for finite binary event distributions. They prove when a single qubit achieves lower total-variation error than every homogeneous two-state edge-emitting hidden Markov model. The key is shared dynamics: one physically feasible recurrence must explain every temporal context. Covering its two-dimensional coefficient region yields classical error lower bounds checked with exact arithmetic. These constraints detect structure missed by rank tests, although satisfying them need not yield a valid classical model. Across six designed quantum constructions, the method certifies candidates left unresolved by the specified clock, rank and complete-model search policies on every construction. On five, it brackets the best classical error within an interval of width 0.025. The comparison concerns persistent-state memory; the qubit remains inexpensive to simulate classically.

Primary area:
learning on time series and dynamical systems
Keywords:
quantum stochastic models, hidden Markov models, finite-state memory, sequence modeling, exact certificates, total variation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_Gqp7OpenReview ↗
Rating
1
Confidence
3(+1)
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

A paper purely generated by AI, and I cannot learn any useful information.

Critical strengths

No

Critical weaknesses

No

Questions for authors

No question

3 comments
Area_Chair_MSSTOpenReview ↗

request for more details/justification

Dear Reviewer Gqp7,

Thank you for your efforts so far. The current review is extremely short (literally 13 words), more details are clearly requested. Given the discussion so far, could you provide more details in your review, which would be more helpful for the committee for the final decision. Specifically, we expect more evidence to support your ratings. You are encouraged for further discussion and/or checking all reviews/rebuttals as well.

Best, AC

Reviewer_Gqp7OpenReview ↗

Reply to AC and authors

Dear AC, thanks for your comment.

Besides its clarity, my current concerns rely on the significance and scope of the contribution: an intrinsically incomplete relaxation, a disconnect between the theoretical separation and the physical experiments, and limited independent evidence from the reported “additional decisions.”

  1. The method has a structural blind spot.

    Consider the length-nn distribution that places exactly one 1 at a uniformly random position: pn(w)=1n 1{#1(w)=1}.p_n(w)=\frac1n\,\mathbf 1\{\#1(w)=1\}. It satisfies both shared feasible recurrences, with coefficient pairs (2,1)(2,1) and (0,0)(0,0), and every compatible prefix-Hankel table has rank at most two. Thus, even infinitely fine coefficient refinement and exact optimization return a zero recurrence lower bound.

    Nevertheless, this law is not realizable by a two-state HMM. Its survival probabilities P(0k)=1−k/nP(0^k)=1-k/n, for k=0,1,2,3k=0,1,2,3, uniquely force the zero-symbol matrix to have trace 22 and determinant 11. Nonnegativity and row-substochasticity then force B0=IB_0=I, contradicting P(0)=1−1/nP(0)=1-1/n. Compactness therefore gives a strictly positive distance from the physical HMM class.

    Consequently, the relaxation admits no general positive multiplicative approximation guarantee for the physical distance. This strengthens the interpretation of the limitation acknowledged in Proposition 4; it does not contradict that proposition. The example concerns arbitrary finite targets, not an established single-qubit realization.

  2. The theoretical advantage over rank tests is not demonstrated on the physical quantum examples.

    Proposition 3 separates shared feasible recurrences from rank-two constraints. However, Appendix B.3 proves that its separating constructions have no homogeneous single-qubit realization for n≥5n\ge5, whereas the experiments use n=8n=8.

    Conversely, Tables D.4a–b report strictly positive rank-based lower bounds for all six physical quantum targets. Since each undegraded candidate equals its target, the rank baseline already certifies the classical nonrealizability of every original target.

    Thus, the examples that rank tests miss are outside the relevant quantum model, while all experimental quantum targets are already detected by rank. The experiments establish larger certified error margins, but do not realize the manuscript’s distinctive theoretical separation within the physical single-qubit setting.

  3. The “162 additional decisions” largely re-express improved lower bounds.

    Let LL be the recurrence lower bound, MM the comparator envelope, and E(η)=TV(p,qη)E(\eta)=TV(p,q_\eta). The constructed degradation path satisfies

    E(1/2)=TV(p,u)\ge d_{\mathrm{HMM2}}(p)\ge L,$$ because its endpoint $u$ is the uniform, classically realizable law. By continuity, whenever $L-M>2\times10^{-4}$, some interior noise rate necessarily satisfies $$M+10^{-4}\le E(\eta)\le L-10^{-4}.$$ This is exactly the additional-decision criterion. A finite grid must still sample the interval, but the existence of such decisions already follows from the improved bound. Their number therefore depends on grid placement and density. These are useful robustness measurements, but provide little independent evidence beyond the underlying improvement in certification strength.
  4. The remaining novelty and practical significance are insufficiently established.

    Quantum memory advantages, finite-sequence memory witnesses, global parameter-grid certification, and the distinction between linear and positive realizations are established in the cited literature. The potentially new contribution is the specific recurrence-based TV certificate and its implementation; I am not claiming that previous work fully subsumes this combination.

    However, the acoustic confirmation is already settled by the earlier clock certificate. The uncorrected orientations account for 139 of 162 additional decisions and succeed on all six constructions, while correction consumes approximately 37–45 seconds without a time-reallocated ablation. External transfer and hardware certification remain unsuccessful.

    Finally, a two-dimensional coefficient domain does not eliminate the 2n2^n probability variables or the (n−2)2n−1+1(n-2)2^{n-1}+1 contexts per orientation. The evidence remains concentrated on short binary sequences and a two-state classical budget, with no demonstrated scalable extension.

AuthorsOpenReview ↗

Response to Reviewer Gqp7's comment and continued request for clarity

Dear Reviewer Gqp7 (and Area Chair MSST),

We appreciate your continued engagement, and hope you can clarify the contradictions below and amend your official review accordingly:

(1) On Nov 13th you wrote that our manuscript lacked the clarity needed to "assess its mathematical correctness and the significance of its contributions," and that your score was final. On Nov 15th, with the manuscript unchanged, you posted a detailed technical assessment of that significance. Could you update your official review, which remains in its unchanged, 13-word form, now that your most recent comment shows the paper can be assessed?

(2) On your provided score for soundness (Soundness = 1: "significant concerns about the paper's soundness that do not appear easy to address"), your comment does not name an error in any theorem, proof, or certificate. You write that your concerns "rely on the significance and scope of the contribution," and that your first point "does not contradict" Proposition 4. Could you help reconcile Soundness = 1 against the absence of identified soundness issues?

(3) You note several strengths in your most recent comment: that our experiments "establish larger certified error margins," that the additional decisions are "useful robustness measurements," and that the paper offers a "potentially new contribution." Still, the official review lists Critical Strengths as "No."

(4) On whether the paper can be read, your comment accurately works through Propositions 3 and 4, Appendix B.3, and Tables D.4a–b, while the official review's summary still states, "I cannot learn any useful information."

Your concerns build on boundaries our paper proves or reports. We agree with your algebra and respond to each below:

(A) Your calculation for pnp_n at ((2,1),(0,0))((2,1),(0,0)) is correct, and as you say, it illustrates Proposition 4. This is not special to our relaxation: the set of HMM2-realizable laws is compact, so any strict outer relaxation (Hankel-rank, spectral, clock) returns 00 for laws inside it that lie at strictly positive TV distance from every physical HMM2, so none admits a global multiplicative guarantee. Instead of claiming one, we certify tightness per instance by pairing the verified lower bound LL with an explicit physical HMM2 upper witness. On five of the six quantum targets, the two are within 0.0250.025 (Figure 3, Appendix D.3). We will add your example next to Proposition 4.

(B) Proposition 3 (Section 4.2) is a non-subsumption result showing that shared feasible recurrences capture constraints that no compatible rank-two Hankel test can. Appendix B.3 is our own proof that its separating constructions have no homogeneous single-qubit realization for n≥5n \ge 5, so we agree with you there. Section 5.2 asks instead about approximate separation on noisy n=8n = 8 single-qubit models. At zero noise, where E(0)=0E(0) = 0, any positive rank bound rules out exact HMM2 realizability. A noisy qubit has E(η)>0E(\eta) > 0, and a bound at or below E(η)E(\eta) cannot exclude an HMM2 that matches or beats it; certifying it requires L>E(η)L > E(\eta), which our recurrence bound supplies at noise rates where the rank bound cannot. Our revision will clarify where Sections 4.2 and 5.2 meet.

(C) We agree with the continuity argument (Table D.2 already flags the grid points as dependent), and our empirical claims do not depend on the grid count: L>ML > M holds on all six constructions, where MM is the comparator envelope, and LL is within 0.0250.025 of the physical upper witness on five. The revision will give the continuous certified η\eta-interval for each target alongside Table D.2.

(D) On novelty, you identify the recurrence-based TV certificate and its implementation as the "potentially new contribution," and state that you are not claiming prior work subsumes it. That certificate, with Propositions 3 and 4, is what we claim.

(E) With the correction disabled, the uncorrected shared-recurrence bound already succeeds on all six constructions and accounts for 139 of the 162 decisions. We have not run a time-matched ablation of the optional correction; the six-of-six result does not use it.

(F) Table 1 presents the acoustic benchmark only as a consistency check against the prior clock witness. Section 5.3 and Appendix F.1 report the negative transfer and hardware results, which show where the certified advantage fails.

(G) On scale, exact TV over length-nn binary words involves 2n2^n probabilities, while the bottleneck for certifying the whole HMM2 class is global non-convexity over transition-emission matrices. We confine that non-convexity to a two-dimensional coefficient cover, where each cell is an LP verified by exact rational duals. At n=8n = 8, this cover is what makes global certification tractable. Scaling beyond two states and short horizons is stated as open in the title, abstract, and limitations.

We ask that the scores be revisited along with the review text.

Best regards,

The Authors

Reviewer_r7hJOpenReview ↗
Rating
2(−1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes an authentication method based on shared recursive constraints, which is designed to show the memory advantage of a single-qubit model over a two-state classical HMM. By employing parameter space partitioning and linear programming, the method computes a lower bound on the total variation error for the entire class of classical models; it also analyzes the advantages and theoretical limitations of this approach instead of rank-based tests.

Critical strengths

This paper provides a lower bound on error that is applicable to an entire class of models, and it is supported by full parameter-space coverage and rigorous formal proofs. This result cannot be replicated simply by retraining a classical HMM.

This paper uses exact math proof for each region while maintaining search boundaries which encompasses the entire classical parameter space. Even if the solver is terminated, the resulting lower bound still remains valid since the certificates pass verification.

Critical weaknesses

The paper establishes a verification method for homogeneous, edge-emitting HMMs with two hidden states. It does not extend to three or more hidden states, nor does it demonstrate computational scalability for long sequences. The additional certifications are demonstrated on hand-designed instances under specific computational policies. The generalization is not being proved.

Questions for authors

These six quantum processes are all purpose-built cases. The rationale behind the selection of these processes needs to be clarified, and to what extent the experimental results are representative of a wider range of stochastic processes?

How much can performance differences between the new approach and existing methods be attributed to the recursive constraints themselves?

2 comments
Reviewer_r7hJOpenReview ↗

Response to author rebuttal and Reviews from other Reviewers

Thanks for the reviewer's feedback. It partially addressed my concerns, but I feel the answer is still a bit superficial in general. It just reiterates what is already shown in the current paper and appendix. I also think Reviewer Gqp7 raised some important concerns that should be addressed more appropriately. I will keep my rating for now, but have a second and final thought later.

Since there is no additional explanation provided by the authors, and my concerns remain, I updated my score to reflect that.

Reviewer_u2PwOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper develops a rule that every homogeneous two-state classical model must satisfy, then uses it to certify cases where a single qubit reproduces finite binary sequences more accurately than any model in that classical class. The key strength is that this rules out the entire model class, rather than merely outperforming whichever classical model happened to be trained.

The paper is also unusually careful about scope. It does not claim computational quantum advantage, admits that the qubit is easy to simulate classically, and shows that larger classical models can perform better. The result is specifically about persistent memory: one qubit versus two classical internal states.

Critical strengths

1) Clean and well-defended contribution. The certificate uses exact arithmetic, does not require trusting solver optimality, and is supported by extensive reproducibility material.

2) Excellent claim discipline. The authors clearly separate the mathematical memory result from practical quantum advantage, classical simulation cost, and hardware performance.

3) Meaningful narrow result. The comparison is limited, but it gives a concrete and certified separation between one-qubit and two-state classical sequence generators. This seems valuable in a field where broader memory comparisons remain difficult.

4) Strong treatment of limitations. The paper explains not only what its certificate detects, but also what it misses, including the fact that satisfying the shared rule does not guarantee a physically realizable classical model.

Critical weaknesses

1) Accessibility. The organization and density of stochastic-model jargon make the main quantum-memory result unnecessarily difficult to extract. A short conceptual explanation distinguishing the physical model, the recurrence relaxation, and the different upper and lower bounds would help considerably.

2) Narrow significance. The acoustic result was already resolved by an earlier certificate, while the new method’s additional value is mainly established on six designed quantum examples. This demonstrates usefulness, but not yet broad applicability.

3) Limited practical evidence. The transfer experiment and separate hardware pilot fail their stated criteria. This does not undermine the mathematical result, but it limits any practical interpretation.

Questions for authors
  1. The paper alternates between an upper bound from an actual fitted classical model and one from a recurrence-consistent distribution that may not correspond to a real model. Could the authors state more directly which bound supports each central claim?

  2. If the intended novelty is not a general quantum advantage or a general bit-versus-qubit information gap, what is the preferred concise statement of novelty? My reading is that it is a certified approximation separation between one persistent qubit and homogeneous two-state classical generators.

  3. How much should the six designed constructions be taken as evidence of future usefulness, rather than existence proofs tailored to the type of obstruction detected by the method?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.