Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete

Andrej Vukovic; Arthur Mehta; Kiera Hutton

REVIEW 2 major objections 2 minor 27 references

Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete

T0 review · 2 major / 2 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read Deciding whether a classical-quantum channel can exactly preserve a single classical bit is QCMA-complete.

desk verdict The witness-characterization lemma is correct and elegant, but the QCMA-completeness claim is unverifiable in this corrupted text and sits in tension with the lemma. read the letter →

arxiv 2508.10664 v1 pith:IRDEKL4F submitted 2025-08-14 quant-ph cs.CCmath.OA

Kiera Hutton , Arthur Mehta , Andrej Vukovic This is my paper

classification quant-phcs.CCmath.OA MSC 68Q1581P68

keywords classical-quantumchannelQCMA-completebitpreservationorthogonality-constrainedoptimizationHilbert-Schmidtoverlapbiquadraticwitnesscharacterizationquantumcomplexitytheory

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

This paper proves that deciding whether a classical-quantum (C-Q) channel can exactly preserve one classical bit is QCMA-complete, meaning it is exactly as hard as problems verifiable by a classical witness plus a quantum proof. It also proves QCMA-completeness for the related task of finding orthogonal input states whose outputs have minimal or maximal Hilbert-Schmidt overlap after passing through the channel. The key step is a complete characterization of which input pairs achieve these extrema: computational basis states for the minimum, and |+>, |-> on a single basis pair for the maximum. This characterization turns a continuous optimization problem into a finite checkable witness, giving concise proofs of completeness for both problems.

What carries the argument

The central device is the complete characterization of optimal witness pairs for the orthogonality-constrained output overlap of a C-Q channel: the minimum is always achieved by computational basis states and the maximum by $|+\rangle, |-\rangle$ on a single basis pair. This reduces an optimization over all orthogonal input pairs to a finite candidate set, enabling a concise witness-based inclusion in QCMA and a hardness reduction from a QCMA-complete problem.

What would settle it

Run numerical optimization over orthogonal pure input pairs for randomly generated small-dimensional C-Q channels (e.g., two- and three-qubit outputs). If any channel yields a maximum Hilbert-Schmidt overlap not achieved by a $|+\rangle, |-\rangle$ pair on a single basis pair, or a minimum not achieved by computational basis states, the characterization lemma is false and the QCMA-completeness proofs collapse.

Watch

Extended reading notes

Core claim

The paper's central claim is that the bit-preservation problem for C-Q channels is QCMA-complete. The proof rests on a matrix-analysis lemma giving a complete characterization of optimal witnesses: for any C-Q channel $\Phi$, the minimum over orthogonal input states $|u\rangle, |v\rangle$ of the Hilbert-Schmidt overlap $\mathrm{Tr}(\Phi(|u\rangle\langle u|)\,\Phi(|v\rangle\langle v|))$ is always attained by computational basis states, and the maximum is always attained by $|+\rangle, |-\rangle$ on a single basis pair. This characterization directly supplies the witnesses needed for the QCMA upper bound and the reduction from a QCMA-complete problem, and it also yields QCMA-completeness for t

Load-bearing premise

The proof depends on the lemma that for every C-Q channel the minimum overlap is attained by computational basis states and the maximum by $|+\rangle, |-\rangle$ on a single basis pair; if even one channel violates this, the completeness reductions fail.

Editorial extensions

If this is right

The bit-preservation decision problem for classical-quantum channels is now known to be exactly QCMA-complete, locating it precisely in the quantum complexity landscape.
The same witness characterization gives QCMA-completeness for the shared orthogonality-constrained optimization: deciding whether orthogonal inputs can be made to have output overlap below a given threshold or above a given threshold.
Because both problems are cast as biquadratic optimization with orthogonality constraints, the result shows that such optimization remains QCMA-hard even under the special structure of C-Q channel outputs.
The characterization supplies finite, checkable witnesses for a continuous optimization problem, which may make channel separation tasks more amenable to verification.

Reading between the lines

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

One could test the characterization numerically on random small-dimensional C-Q channels: if any instance attains its minimum or maximum overlap at a pair other than the claimed simple forms, the load-bearing lemma would fail.
The matrix-analysis method might extend to other orthogonality-constrained channel optima, such as trace-distance separation, potentially yielding completeness results for adjacent complexity classes like QMA(2).
If the characterization generalizes beyond C-Q channels to fully quantum channels, the bit-preservation decision might become complete for a class higher than QCMA.

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.

Desk Editor's Note

read the letter

Colleague—

The one thing you should know: the headline lemma is real. Under the standard model of a c-q channel (linear extension of a classical-to-quantum map), the characterization of optimal witnesses—computational basis states for the minimum overlap, |+>,|-> on a single pair for the maximum—is correct. I checked the stress-test note's inequality proof myself; it goes through with simple matrix inequalities. That is a genuinely nice observation and probably the most citable part of the paper.

The novelty is the claimed QCMA-completeness of bit-preservation. I could not verify it: the supplied full text is corrupted, so the reductions are unreadable. That alone would make me desk-reject a submission in this state. But there is a deeper worry. If the minimum overlap is always achieved by a pair of basis states, then the bit-preservation decision problem reduces to searching over pairs (i,j) of basis states. When the channel is given by explicit matrices, that search is polynomial. When the channel is given as a circuit, the search is over exponentially many pairs, but the witness is still a classical pair of indices; a quantum witness cannot beat that because acceptance probability is a convex combination of pair-wise checks. That suggests the problem sits in NP (with a BQP verifier), not at the QCMA-complete level. The abstract does not specify the input model or a promise gap that would make the search genuinely quantum-witness-hard. If the authors can close that gap, the paper becomes very interesting; if not, the complexity classification is wrong.

There is also a minor framing issue: the abstract calls this biquadratic optimization with orthogonality constraints, but the characterization makes the constraints irrelevant for the optimum. That framing misleads.

Bottom line: the paper deserves a serious referee once the text is readable and the complexity question is addressed. The lemma is worth citing now. If it lands in a good venue, I'd bring it to the reading group to see how they resolve the QCMA tension. In its current corrupted form, it is not refereable. The right move is to ask for a clean PDF and a response to the basis-search tension.

Referee Report

2 major / 2 minor

Summary. The paper claims two QCMA-completeness results: (i) deciding whether a classical-quantum (C-Q) channel can exactly preserve a single classical bit, and (ii) deciding related orthogonality-constrained optimization problems over C-Q channels where the Hilbert-Schmidt overlap of the outputs of orthogonal inputs is minimized or maximized. The main technical contribution is said to be a complete characterization of the optimal witnesses: computational basis states for the minimum overlap, and |+>, |-> states on a single basis pair for the maximum overlap. The proofs are described as reductions to a known QCMA-complete problem together with a witness lemma established by matrix analysis. The supplied full text is, however, corrupted and unreadable beyond isolated fragments, so almost none of the derivations can be inspected.

Significance. If the results are correct, they give a natural quantum-information problem—exact bit preservation through a C-Q channel—a precise complexity classification as QCMA-complete, and they identify two new QCMA-complete problems in orthogonality-constrained overlap optimization. The promised characterization of optimal witnesses would be a genuinely useful structural result, with consequences for how such optimization problems can be reduced. The proof strategy outlined in the abstract is standard in style and plausible. However, the current manuscript provides no inspectable derivations, no machine-checked proofs, and no reproducible code; the significance therefore rests entirely on the unverified assertions in the abstract.

major comments (2)

[Full text (entire supplied manuscript)] The full text is corrupted and unreadable: the text appears as mojibake, and no equation, section, or proof can be checked. The central claims—QCMA-completeness for bit preservation and the complete witness characterization—are load-bearing and are asserted but not verifiable in this copy. This is a verification gap, not a mathematical objection, but it prevents any soundness assessment. A clean, readable manuscript is required before the technical content can be evaluated.
[Abstract / main technical lemma] The claimed complete characterization of optimal witnesses is the pivotal step. If it were false that the minimum overlap is always achieved by computational basis states and the maximum by |+>,|-> on a single basis pair, then both reductions would fail. The abstract gives no proof or even the precise statement of the lemma (e.g., whether it holds for all C-Q channels, all dimensions, and both exact and approximate versions). The only fragments visible in the corrupted text include the overlap condition Tr(Φ(|u><u|) Φ(|v><v|)) = 0 and a definition involving ηtr(Φ), but no derivation is readable. The lemma must be stated fully and proved in a verifiable manner.

minor comments (2)

[Abstract] The abstract states both problems 'can be cast as biquadratic optimization with orthogonality constraints,' but the explicit formulation and the exact/approximate threshold parameters are not visible. Please specify the decision versions precisely, including any promise gap.
[General presentation] The corrupted text contains numbered sections and displayed equations that cannot be mapped to readable content. This is not a content issue, but it currently makes the manuscript unusable as a submission; please ensure the PDF text extraction is clean.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified; the QCMA-completeness claim rests on a separate witness-characterization theorem, not on a definitional restatement or self-citation chain.

full rationale

The abstract's derivation chain is: (i) define bit-preservation for C-Q channels as an orthogonality-constrained overlap optimization problem; (ii) prove a matrix-analysis lemma characterizing the optimal witnesses (computational basis states for the minimum, and |+>, |-> on a single basis pair for the maximum); (iii) use that characterization to give QCMA-completeness proofs. None of these steps reduces to its own input by construction. The optimization problem is not defined as 'the minimum is achieved on the computational basis'—that is the content of the lemma, a separate mathematical statement that could in principle fail. The completeness proof is stated as reducing from an established QCMA-complete problem and then applying the lemma, which is the standard direction of a hardness reduction rather than a renamed version of the target. No fitted parameter is renamed as a prediction, and no load-bearing self-citation or imported uniqueness theorem is visible in the abstract or the readable fragments. The supplied full text is heavily corrupted, so no section or equation could be inspected for hidden self-referential steps; this is a verification gap, not evidence of circularity. Under the rule that circularity is claimed only when a specific reduction can be quoted, the appropriate finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The abstract does not introduce new entities; it relies on standard complexity class definitions and the channel model.

assumptions (3)

standard math Standard definition of the QCMA complexity class and its complete problems
Completeness is defined relative to this class; the paper assumes the standard definitions.
domain assumption C-Q channel model with Hilbert-Schmidt inner product as the overlap measure
The results are stated for this specific mathematical model of channels and distinguishability.
standard math Existence of a known QCMA-complete problem used in the reduction
The completeness proof requires a starting complete problem, presumably from prior literature (not visible in the abstract).

how reviews work

0 comments

Cite this review

Pith. "Pith review of Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete." pith.science (2026). https://pith.science/paper/IRDEKL4F

@misc{pith2026250810664,
  author       = {Pith},
  title        = {Pith review of: Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IRDEKL4F}},
  note         = {Machine review of arXiv:2508.10664}
}

read the original abstract

We prove that deciding whether a classical-quantum (C-Q) channel can exactly preserve a single classical bit is QCMA-complete. This "bit-preservation" problem is a special case of orthogonality-constrained optimization tasks over C-Q channels, in which one seeks orthogonal input states whose outputs have small or large Hilbert-Schmidt overlap after passing through the channel. Both problems can be cast as biquadratic optimization with orthogonality constraints. Our main technical contribution uses tools from matrix analysis to give a complete characterization of the optimal witnesses: computational basis states for the minimum, and |+>, |-> over a single basis pair for the maximum. Using this characterization, we give concise proofs of QCMA-completeness for both problems.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

27 extracted references · 15 canonical work pages

[1]

Absil, R

P.-A. Absil, R. Mahony, and R. Sepulchre. Optimization A lgorithms on M atrix M anifolds . Princeton University Press, 2008

work page 2008
[2]

Aharonov and T

D. Aharonov and T. Naveh. Quantum NP - A S urvey, 2002. Available at https://arxiv.org/abs/quant-ph/0210077

arXiv 2002
[3]

H. Bauer. Minimalstellen von F unktionen und E xtremalpunkte. Archiv der Mathematik , 9: 389--393, 1958. \\ DOI:\,10.1007/BF01898615 http://dx.doi.org/10.1007/BF01898615

work page doi:10.1007/bf01898615 1958
[4]

Buhrman, R

H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Q uantum F ingerprinting. Phys. Rev. Lett. , 87: 167902, 2001. \\ DOI:\,10.1103/PhysRevLett.87.167902 http://dx.doi.org/10.1103/PhysRevLett.87.167902

doi:10.1103/physrevlett.87.167902 2001
[5]

A. D. Bookatz. QMA -complete problems, 2013. \\ Online: https://arxiv.org/abs/1212.6312

work page Pith review arXiv 2013
[6]

Beigi and P

S. Beigi and P. W. Shor. On the C omplexity of C omputing Z ero- E rror and H olevo C apacity of Q uantum C hannels, 2008. \\ arXiv:\,0709.2090 http://arxiv.org/abs/0709.2090

arXiv 2008
[7]

Culf and A

E. Culf and A. Mehta. New A pproaches to C omplexity via Q uantum G raphs, 2023. \\ Online: https://arxiv.org/abs/2309.12887

arXiv 2023
[8]

Chailloux and O

A. Chailloux and O. Sattath. The C omplexity of the S eparable H amiltonian P roblem. In 2012 IEEE 27th Conference on Computational Complexity . IEEE , 2012. \\ DOI:\,10.1109/ccc.2012.42 http://dx.doi.org/10.1109/ccc.2012.42

doi:10.1109/ccc.2012.42 2012

Show all 27 references

[9]

Delsol, O

I. Delsol, O. Fawzi, J. Kochanowski, and A. Ramachandran. Computational aspects of the trace norm contraction coefficient, 2025. \\ Online: https://arxiv.org/abs/2507.16737

2025
[10]

R. Duan, S. Severini, and A. Winter. Zero- E rror C ommunication via Q uantum C hannels, N oncommutative G raphs, and a Q uantum L ov\' a sz N umber. IEEE Transactions on Information Theory , 59(2): 1164--1174, 2013. \\ DOI:\,10.1109/tit.2012.2221677 http://dx.doi.org/10.1109/...

2013
[11]

Edelman, T

A. Edelman, T. A. Arias, and S. T. Smith. The G eometry of A lgorithms with O rthogonality C onstraints. SIAM Journal on Matrix Analysis and Applications , 20(2): 303--353, 1998. \\ DOI:\,10.1137/S0895479895290954 http://dx.doi.org/10.1137/S0895479895290954

1998 doi
[12]

P. Ganesan. Spectral bounds for the quantum chromatic number of quantum graphs. Linear Algebra and its Applications , 674: 351--376, 2023. \\ DOI:\,https://doi.org/10.1016/j.laa.2023.06.007 http://dx.doi.org/https://doi.org/10.1016/j.laa.2023.06.007

2023 doi
[13]

Gharibian

S. Gharibian. Guest C olumn: T he 7 faces of quantum NP . SIGACT News , 54(4): 54–91, 2024. \\ DOI:\,10.1145/3639528.3639535 http://dx.doi.org/10.1145/3639528.3639535

2024
[14]

Gutoski, P

G. Gutoski, P. Hayden, K. Milner, and M. M. Wilde. Quantum interactive proofs and the complexity of separability testing. Theory of Computing , 11(1): 59--103, 2015. \\ DOI:\,10.4086/toc.2015.v011a003 http://dx.doi.org/10.4086/toc.2015.v011a003

2015 doi
[15]

Gharibian and J

S. Gharibian and J. Sikora. Ground S tate C onnectivity of L ocal H amiltonians , page 617–628. Springer Berlin Heidelberg, 2015. \\ DOI:\,10.1007/978-3-662-47672-7\_50 http://dx.doi.org/10.1007/978-3-662-47672-7\_50

2015 doi
[16]

J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu. S ample- O ptimal T omography of Q uantum S tates. IEEE Transactions on Information Theory , 63(9): 5628--5641, 2017. \\ DOI:\,10.1109/TIT.2017.2719044 http://dx.doi.org/10.1109/TIT.2017.2719044

2017
[17]

A. Horn. Doubly S tochastic M atrices and the D iagonal of a R otation M atrix. American Journal of Mathematics , 76(3): 620--630, 1954. \\ Online: http://www.jstor.org/stable/2372705

1954
[18]

Horodecki, P

M. Horodecki, P. W. Shor, and M. B. Ruskai. Entanglement B reaking C hannels. Reviews in Mathematical Physics , 15(06): 629--641, 2003. \\ DOI:\,10.1142/s0129055x03001709 http://dx.doi.org/10.1142/s0129055x03001709

2003 doi
[19]

S. P. Jordan, H. Kobayashi, D. Nagaj, and H. Nishimura. Achieving perfect completeness in classical-witness quantum M erlin- A rthur proof systems. Quantum Info. Comput. , 12(5–6): 461–471, 2012

2012
[20]

C. Ling, J. Nie, L. Qi, and Y. Ye. Biquadratic O ptimization O ver U nit S pheres and S emidefinite P rogramming R elaxations. SIAM Journal on Optimization , 20(3): 1286--1310, 2010. \\ DOI:\,10.1137/080729104 http://dx.doi.org/10.1137/080729104

2010 doi
[21]

J. Matsuda. Algebraic C onnectedness and B ipartiteness of Q uantum G raphs. Communications in Mathematical Physics , 405(8): 185, 2024. \\ DOI:\,10.1007/s00220-024-05046-y http://dx.doi.org/10.1007/s00220-024-05046-y

2024 doi
[22]

M. A. Nielsen and I. L. Chuang. Quantum C omputation and Q uantum I nformation . Cambridge University Press, 2000

2000
[23]

I. Schur. \"U ber eine K lasse von M ittelbildungen mit A nwendungen auf die D eterminantentheorie. Sitzungsberichte der Berliner Mathematischen Gesellschaft , 22: 9--20, 1923

1923
[24]

D. Stahlke. Quantum Z ero- E rror S ource- C hannel C oding and N on- C ommutative G raph T heory. IEEE Transactions on Information Theory , 62(1): 554--577, 2016. \\ DOI:\,10.1109/tit.2015.2496377 http://dx.doi.org/10.1109/tit.2015.2496377

2016
[25]

M. H. Veatch. Linear and C onvex O ptimization: A M athematical A pproach . Wiley, 1 edition, 2021

2021
[26]

J. Watrous. The T heory of Q uantum I nformation . Cambridge University Press, 1 st edition, 2018

2018
[27]

Wen and W

Z. Wen and W. Yin. A F easible M ethod for O ptimization with O rthogonality C onstraints. Mathematical Programming , 142(1--2), 2013. \\ DOI:\,10.1007/s10107-012-0584-1 http://dx.doi.org/10.1007/s10107-012-0584-1

2013 doi

Pith tools

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

[1] [1]

Absil, R

P.-A. Absil, R. Mahony, and R. Sepulchre. Optimization A lgorithms on M atrix M anifolds . Princeton University Press, 2008

work page 2008

[2] [2]

Aharonov and T

D. Aharonov and T. Naveh. Quantum NP - A S urvey, 2002. Available at https://arxiv.org/abs/quant-ph/0210077

arXiv 2002

[3] [3]

H. Bauer. Minimalstellen von F unktionen und E xtremalpunkte. Archiv der Mathematik , 9: 389--393, 1958. \\ DOI:\,10.1007/BF01898615 http://dx.doi.org/10.1007/BF01898615

work page doi:10.1007/bf01898615 1958

[4] [4]

Buhrman, R

H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Q uantum F ingerprinting. Phys. Rev. Lett. , 87: 167902, 2001. \\ DOI:\,10.1103/PhysRevLett.87.167902 http://dx.doi.org/10.1103/PhysRevLett.87.167902

doi:10.1103/physrevlett.87.167902 2001

[5] [5]

A. D. Bookatz. QMA -complete problems, 2013. \\ Online: https://arxiv.org/abs/1212.6312

work page Pith review arXiv 2013

[6] [6]

Beigi and P

S. Beigi and P. W. Shor. On the C omplexity of C omputing Z ero- E rror and H olevo C apacity of Q uantum C hannels, 2008. \\ arXiv:\,0709.2090 http://arxiv.org/abs/0709.2090

arXiv 2008

[7] [7]

Culf and A

E. Culf and A. Mehta. New A pproaches to C omplexity via Q uantum G raphs, 2023. \\ Online: https://arxiv.org/abs/2309.12887

arXiv 2023

[8] [8]

Chailloux and O

A. Chailloux and O. Sattath. The C omplexity of the S eparable H amiltonian P roblem. In 2012 IEEE 27th Conference on Computational Complexity . IEEE , 2012. \\ DOI:\,10.1109/ccc.2012.42 http://dx.doi.org/10.1109/ccc.2012.42

doi:10.1109/ccc.2012.42 2012