Quantum Uncomputation of Clean and Dirty Ancilla Qubits

• URL: http://arxiv.org/abs/2608.09578v1
• Date: Mon, 10 Aug 2026 13:13:54 GMT
• Title: Quantum Uncomputation of Clean and Dirty Ancilla Qubits
• Abstract summary: We present a unified formalization of the uncomputation of both clean and dirty ancillas.<n>We introduce two complementary synthesis-oriented existence-checking methods.<n>Compared to the state-of-the-art Reqompcitereqomp, RwUn achieves 100% coverage on practical complex-dependency benchmarks.
• Score: 1.6179458386967447
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Automatic uncomputation aims to provide programming-language-level support to facilitate the correct and safe use of ancilla qubits in quantum computing, but efforts have only been made for clean ancillas, leaving dirty ancillas unexplored. We present a unified formalization of the uncomputation of both clean and dirty ancillas. For the first time, we prove that checking the existence of uncomputation is coNP-hard. We introduce two complementary synthesis-oriented existence-checking methods: a rewrite-based normalization algorithm (RwUn) and a template-based reasoning system (TpUn) that guarantees uncomputation through structured Store-Use patterns. We implement prototypes of both methods in Qiskit and Python. Compared to the state-of-the-art Reqomp~\cite{reqomp}, RwUn achieves 100% coverage on practical complex-dependency benchmarks, twice the coverage on random classical circuits, and about 50% coverage on random quantum circuits beyond the scope of existing methods, demonstrating broader applicability.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• A Reservoir Computing Approach to Quantum Gate Synthesis [0.0]
  Group Reservoir Computing is an efficient machine-learning paradigm for learning temporal dynamics.<n>We prove that the reconstructed dynamics always remain unitary by construction.<n>The method applies to any finite-dimensional hardware platform.
  arXiv  Detail & Related papers  (2026-07-15T14:34:25Z)
• A Modular Approach to Succinct Arguments for QMA [17.20526790095253]
  We develop a new framework that broadens the cryptographic foundations of succinct arguments for QMA.<n>In particular, we obtain the first succinct, classically-verifiable argument system for QMA which does not rely on the hardness of LWE.<n>Our compiler extends a quantum rigidity-based communication compression technique of Zhang (QCrypt 25)
  arXiv  Detail & Related papers  (2026-06-03T21:38:23Z)
• Q-LEAK: Quantum-Based LEAKage Verification for Side-Channel Countermeasures [2.5435687567731926]
  We propose Q-LEAK, a quantum-based verification approach using Grover's algorithm.<n>Q-LEAK consistently recovered a satisfying assignment within 1-4 tries, with marked bitstrings amplified clearly above the background distribution.<n>The evaluation of Q-LEAK on real quantum hardware revealed at least one classically verified SAT assignment, despite the presence of noise.
  arXiv  Detail & Related papers  (2026-05-25T11:36:19Z)
• Efficient equivalence checking of Clifford-U circuits with shared single-qubit unitaries [5.016480897268685]
  We present an equivalence-checking method for circuits formed by arbitrary single-qubit layers interleaved with Clifford layers.<n>This pattern is common in variational quantum algorithms and Hamiltonian simulation via Trotter decomposition.<n>We prove the existence of an efficient classical algorithm that determines whether a pair of circuits with shared single-qubit layers are equivalent for every possible choice of the shared single-qubit unitaries.
  arXiv  Detail & Related papers  (2026-03-13T06:25:26Z)
• On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation [44.084531611147305]
  We provide a refined convergence analysis of the Single-loop Approximate Implicit Differentiation (SSAID) algorithm.<n>Our result is noteworthy in two aspects: (i) it matches the optimal $mathcalO(-2)$ rate of state-of-the-art multi-loop methods; and (ii) it provides the first explicit, fine-grained characterization of the $$-dependence.
  arXiv  Detail & Related papers  (2026-02-27T03:12:08Z)
• A Posteriori Certification Framework for Generalized Quantum Arimoto-Blahut Algorithms [41.15017547767954]
  We introduce an a posteriori certification viewpoint for the generalized quantum Arimoto-Blahut (QAB) algorithm.<n>We prove a global convergence theorem showing that, under convexity and a substantially weaker numerically verifiable condition, the QAB iteration converges to the global minimizer.<n>As an application, we develop a certified iterative scheme for computing the quantum relative entropy of channels.
  arXiv  Detail & Related papers  (2026-01-14T09:10:41Z)
• Non-Unitary Quantum Machine Learning [0.0]
  We introduce several probabilistic quantum algorithms that overcome the normal unitary restrictions in quantum machine learning. We show that residual connections between layers of a variational ansatz can prevent barren plateaus in models which would otherwise contain them. We also demonstrate a novel rotationally invariant encoding for point cloud data via Schur-Weyl duality.
  arXiv  Detail & Related papers  (2024-05-27T17:42:02Z)
• Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithms [31.478874616470048]
  We study the computational problem of the stationarity test for the empirical loss of neural networks with ReLU activation functions. We show that checking a certain first-order approximate stationarity concept for a piecewise linear function is co-NP-hard. We introduce an algorithmic scheme to test near-approximate stationarity in terms of both Clarke and Fr'echet subdifferentials.
  arXiv  Detail & Related papers  (2023-02-23T17:26:51Z)
• Gradient-descent quantum process tomography by learning Kraus operators [63.69764116066747]
  We perform quantum process tomography (QPT) for both discrete- and continuous-variable quantum systems. We use a constrained gradient-descent (GD) approach on the so-called Stiefel manifold during optimization to obtain the Kraus operators. The GD-QPT matches the performance of both compressed-sensing (CS) and projected least-squares (PLS) QPT in benchmarks with two-qubit random processes.
  arXiv  Detail & Related papers  (2022-08-01T12:48:48Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  "Interactions" between a prover and a verifier can bridge the gap between verifiability and implementation. We demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer.
  arXiv  Detail & Related papers  (2021-12-09T19:00:00Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• QUANTIFY: A framework for resource analysis and design verification of quantum circuits [69.43216268165402]
  QUANTIFY is an open-source framework for the quantitative analysis of quantum circuits. It is based on Google Cirq and is developed with Clifford+T circuits in mind. For benchmarking purposes QUANTIFY includes quantum memory and quantum arithmetic circuits.
  arXiv  Detail & Related papers  (2020-07-21T15:36:25Z)

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.