Rise of conditionally clean ancillae for efficient quantum circuit constructions

• URL: http://arxiv.org/abs/2407.17966v2
• Date: Tue, 20 May 2025 02:51:14 GMT
• Title: Rise of conditionally clean ancillae for efficient quantum circuit constructions
• Authors: Tanuj Khattar, Craig Gidney,
• Abstract summary: We introduce conditionally clean ancilla qubits, a new quantum resource, recently explored by [NZS24], that bridges the gap between traditional clean and dirty ancillae.<n>They begin and end in an unknown state and can be borrowed from existing system qubits, avoiding the space overhead of explicit qubit allocation.<n>We present new circuit constructions leveraging conditionally clean ancillae to achieve lower gate counts and iteration, particularly with limited ancilla availability.
• Score: 0.06640389895742692
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce conditionally clean ancilla qubits, a new quantum resource, recently explored by [NZS24], that bridges the gap between traditional clean and dirty ancillae. Like dirty ancillae, they begin and end in an unknown state and can be borrowed from existing system qubits, avoiding the space overhead of explicit qubit allocation. Like clean ancillae, they can be treated as initialized in a known state within specific computations, thus avoiding the overhead of toggle detection required for dirty ancillae. We present new circuit constructions leveraging conditionally clean ancillae to achieve lower gate counts and depths, particularly with limited ancilla availability. Specifically, we provide constructions for: (a) $n$-controlled NOT using $2n$ Toffolis and $O(\log{n})$ depth given 2 clean ancillae. (b) $n$-qubit incrementer using $3n$ Toffolis given $\log_2^*{n}$ clean ancillae. (c) $n$-qubit quantum-classical comparator using $3n$ Toffolis given $\log_2^*{n}$ clean ancillae. (d) unary iteration over $[0,N)$ using $2.5N$ Toffolis given $\log_2^*{n}$ clean ancillae. (e) unary iteration via skew tree over $[0, N)$ using $1.25N$ Toffolis given $n$ dirty ancillae. We also introduce laddered toggle detection, a technique to replace clean ancillae with dirty ancillae in all our constructions, incurring a 2x Toffoli gate overhead. Our results demonstrate that conditionally clean ancillae are a valuable tool for quantum circuit design, especially in the resource-constrained early fault-tolerant era.

Related papers

• A Classical-Quantum Adder with Constant Workspace and Linear Gates [0.03922370499388702]
  I construct an adder that uses 3 clean ancillae and $4n pm O(1)$ Toffoli gates to add a classical offset into a quantum register.<n>I show that applying the presented adders conditioned on a control qubit requires no additional workspace or Toffolis.
  arXiv  Detail & Related papers  (2025-07-30T20:24:03Z)
• An Uncertainty Principle for Linear Recurrent Neural Networks [54.13281679205581]
  We build a linear filter of order $S$ that approximates the filter that looks $K$ time steps in the past.<n>We fully characterize the problem by providing lower bounds of approximation, as well as explicit filters that achieve this lower bound up to constants.<n>The optimal performance highlights an uncertainty principle: the filter has to average values around the $K$-th time step in the past with a range(width) that is proportional to $K/S$.
  arXiv  Detail & Related papers  (2025-02-13T13:01:46Z)
• Ancilla-free Quantum Adder with Sublinear Depth [2.784223169208082]
  We present the first exact quantum adder with sublinear depth and no ancilla qubits. Our construction is based on classical reversible logic only.
  arXiv  Detail & Related papers  (2025-01-28T09:05:49Z)
• Quantum schoolbook multiplication with fewer Toffoli gates [0.0]
  Controlled n-qubit add-subtract circuits perform an addition when the control qubit is one and a subtraction when it is zero. Schoolbook multiplication yields the lowest Toffoli counts for small register sizes.
  arXiv  Detail & Related papers  (2024-10-01T17:39:24Z)
• Error filtration from optimized quantum circuit interference [0.0]
  We develop an optimized hardware strategy to mitigate errors in a noisy qubit. Our scheme builds on the physical principle of error filtration and exploits auxiliary qubits.
  arXiv  Detail & Related papers  (2024-09-02T17:58:44Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose arbitrary exponentials into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions. We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Scalable improvement of the generalized Toffoli gate realization using trapped-ion-based qutrits [32.33017977520031]
  Direct realizations of the Toffoli gate require either a prohibitive growth of the number of two-qubit gates or using ancilla qubits. Here we experimentally demonstrate a scalable improvement of the realization of the Toffoli gate using trapped-ion-based dual-type optic-microwave qutrits.
  arXiv  Detail & Related papers  (2024-07-10T15:34:56Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Polylogarithmic-depth controlled-NOT gates without ancilla qubits [0.0]
  Controlled operations are fundamental building blocks of quantum algorithms. Decomposing $n$-control-NOT gates into arbitrary single-qubit and CNOT gates is a crucial but non-trivial task.
  arXiv  Detail & Related papers  (2023-12-20T17:23:11Z)
• Modifying $n$-qubit controlled-$ZX$ gate to be $n$-qubit Toffoli gate [3.803244458097104]
  decomposition for controlled-$ZX$ gate in [Phys. Rev. A, 87, 062318 (2013)] has a shallow circuit depth $8n-20$ with no ancilla. We show that the circuit after decomposition can be easily constructed in present physical systems.
  arXiv  Detail & Related papers  (2023-05-24T10:58:54Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
  arXiv  Detail & Related papers  (2023-02-13T22:51:07Z)
• On Fault Tolerance of Circuits with Intermediate Qutrit-assisted Gate Decomposition [3.452050192629253]
  An intermediate qutrit implies that a qubit is operated as a qutrit in a particular execution cycle. We study the challenges of including fault-tolerance in such a decomposition.
  arXiv  Detail & Related papers  (2022-12-15T14:33:45Z)
• Quantum Fourier Addition, Simplified to Toffoli Addition [92.18777020401484]
  We present the first systematic translation of the QFT-addition circuit into a Toffoli-based adder. Instead of using approximate decompositions of the gates from the QFT circuit, it is more efficient to merge gates.
  arXiv  Detail & Related papers  (2022-09-30T02:36:42Z)
• Toward Trainability of Deep Quantum Neural Networks [87.04438831673063]
  Quantum Neural Networks (QNNs) with random structures have poor trainability due to the exponentially vanishing gradient as the circuit depth and the qubit number increase. We provide the first viable solution to the vanishing gradient problem for deep QNNs with theoretical guarantees.
  arXiv  Detail & Related papers  (2021-12-30T10:27:08Z)
• 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)
• Neural networks with superexpressive activations and integer weights [91.3755431537592]
  An example of an activation function $sigma$ is given such that networks with activations $sigma, lfloorcdotrfloor$, integer weights and a fixed architecture is given. The range of integer weights required for $varepsilon$-approximation of H"older continuous functions is derived.
  arXiv  Detail & Related papers  (2021-05-20T17:29:08Z)
• Halving the width of Toffoli based constant modular addition to n+3 qubits [69.43216268165402]
  We present an arithmetic circuit performing constant modular addition having $mathcalO(n)$ depth of Toffoli gates. This is an improvement by a factor of two compared to the width of the state-of-the-art Toffoli-based constant modular adder.
  arXiv  Detail & Related papers  (2021-02-06T17:07:48Z)
• On the realistic worst case analysis of quantum arithmetic circuits [69.43216268165402]
  We show that commonly held intuitions when designing quantum circuits can be misleading. We show that reducing the T-count can increase the total depth. We illustrate our method on addition and multiplication circuits using ripple-carry.
  arXiv  Detail & Related papers  (2021-01-12T21:36:16Z)
• Shuffling Recurrent Neural Networks [97.72614340294547]
  We propose a novel recurrent neural network model, where the hidden state $h_t$ is obtained by permuting the vector elements of the previous hidden state $h_t-1$. In our model, the prediction is given by a second learned function, which is applied to the hidden state $s(h_t)$.
  arXiv  Detail & Related papers  (2020-07-14T19:36:10Z)
• Efficient Quantum Circuit Decompositions via Intermediate Qudits [5.377885520874246]
  We show a method to generate ancilla out of idle qubits by placing some in higher-value states, called qudits. Quantum computers will be resource-constrained for years to come so reducing ancilla requirements is crucial.
  arXiv  Detail & Related papers  (2020-02-24T23:37:24Z)
• Efficient Two-Qubit Pulse Sequences Beyond CNOT [0.0]
  We design efficient controlled-rotation gates with arbitrary angle acting on three-spin encoded qubits for exchange-only quantum computation. We build two-qubit sequences out of subsequences with special properties that render each step of the construction analytically tractable.
  arXiv  Detail & Related papers  (2020-01-25T17:38:14Z)

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.