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

• URL: http://arxiv.org/abs/2508.10664v1
• Date: Thu, 14 Aug 2025 14:03:38 GMT
• Title: Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete
• Authors: Kiera Hutton, Arthur Mehta, Andrej Vukovic,
• Abstract summary: We prove that deciding whether a classical-quantum (C-Q) channel can exactly preserve a single classical bit is QCMA-complete.<n>This "bit-preservation" problem is a special case of orthogonality-constrained optimization tasks over C-Q channels.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Semidefinite Programming for Quantum Channel Learning [35.18016233072556]
  Semidefinite Programming (SDP) can be applied to solve the fidelity optimization problem with respect to the Choi matrix.<n>We have tested several commercially available SDP solvers, all of which allowed for the reconstruction of quantum channels of different forms.<n>This suggests that a relatively small Kraus rank quantum channel is typically sufficient to describe experimentally observed classical data.
  arXiv  Detail & Related papers  (2026-01-18T17:26:45Z)
• Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem [2.4968861883180447]
  Finding ground state solutions of diagonal Hamiltonians is relevant for both theoretical as well as practical problems of interest in many domains such as finance, physics and computer science. Here we use imaginary time evolution through a new block encoding scheme to obtain the ground state of such problems and apply our method to MaxCut as an illustration.
  arXiv  Detail & Related papers  (2024-11-16T08:17:36Z)
• Optimization by Decoded Quantum Interferometry [42.169154389732036]
  We introduce a quantum algorithm called Decoded Quantum Interferometry (DQI)<n>For approximating to data over finite fields, DQI achieves a better approximation ratio than any time known to us.
  arXiv  Detail & Related papers  (2024-08-15T17:47:42Z)
• Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA [0.0]
  In this work, an implementation of the QAOA2 method for the scalable solution of the MaxCut problem is presented. The limits of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA are investigated. Results from large-scale simulations of up to 33 qubits are presented, showing the advantage of QAOA in certain cases and the efficiency of the implementation.
  arXiv  Detail & Related papers  (2024-06-25T09:02:31Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization [44.96576908957141]
  We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linear iterations problems on quantum computers.
  arXiv  Detail & Related papers  (2022-03-23T18:00:03Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space. We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states. Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
  arXiv  Detail & Related papers  (2022-03-11T17:19:26Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Classically optimal variational quantum algorithms [0.0]
  Hybrid quantum-classical algorithms, such as variational quantum algorithms (VQA), are suitable for implementation on NISQ computers. In this Letter we expand an implicit step of VQAs: the classical pre-computation subroutine which can non-trivially use classical algorithms to simplify, transform, or specify problem instance-specific variational quantum circuits.
  arXiv  Detail & Related papers  (2021-03-31T13:33:38Z)
• DAGs with No Fears: A Closer Look at Continuous Optimization for Learning Bayesian Networks [45.3591788771536]
  We re-examine a continuous optimization framework dubbed NOTEARS for learning Bayesian networks. We show that the Karush-Kuhn-Tucker optimality conditions for the NOTEARS cannot be satisfied except in a trivial case. Some combinations with local search are both more accurate and more efficient than the original NOTEARS.
  arXiv  Detail & Related papers  (2020-10-18T22:59:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.