Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909736930115584 |
|---|---|
| author | Hutton, Kiera Mehta, Arthur Vukovic, Andrej |
| author_facet | Hutton, Kiera Mehta, Arthur Vukovic, Andrej |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_10664 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete Hutton, Kiera Mehta, Arthur Vukovic, Andrej Quantum Physics Computational Complexity Operator Algebras 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. |
| title | Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete |
| topic | Quantum Physics Computational Complexity Operator Algebras |
| url | https://arxiv.org/abs/2508.10664 |