We present the first exact quantum adder with sublinear depth and no ancilla qubits. Our construction is based on classical reversible logic only and employs low-depth implementations for the \(\textsf{CNOT}\) ladder operator and the Toffoli ladder operator, two key components to perform ripple-carry addition. Namely, we demonstrate that any ladder of n \(\textsf{CNOT}\) gates can be replaced by a \(\textsf{CNOT}\) -circuit with \(O\left( \log n \right) \) depth, while maintaining a linear number of gates. We then generalize this construction to Toffoli gates and demonstrate that any ladder of n Toffoli gates can be substituted with a circuit with \(O\left( \log ^2 n \right) \) depth while utilizing a linearithmic number of gates. This builds on the recent works of Nie \(et \; al.\) [13] and Khattar and Gidney [10] on the technique of conditionally clean ancillae. By combining these two key elements, we present a novel approach to design quantum adders that can perform the addition of two n-bit numbers in depth \(O\left( \log ^2 n \right) \) without the use of any ancilla and using classical reversible logic only (Toffoli, \(\textsf{CNOT}\) and \(\textsf{X}\) gates).

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Ancilla-Free Quantum Adder with Sublinear Depth

  • Maxime Remaud,
  • Vivien Vandaele

摘要

We present the first exact quantum adder with sublinear depth and no ancilla qubits. Our construction is based on classical reversible logic only and employs low-depth implementations for the \(\textsf{CNOT}\) ladder operator and the Toffoli ladder operator, two key components to perform ripple-carry addition. Namely, we demonstrate that any ladder of n \(\textsf{CNOT}\) gates can be replaced by a \(\textsf{CNOT}\) -circuit with \(O\left( \log n \right) \) depth, while maintaining a linear number of gates. We then generalize this construction to Toffoli gates and demonstrate that any ladder of n Toffoli gates can be substituted with a circuit with \(O\left( \log ^2 n \right) \) depth while utilizing a linearithmic number of gates. This builds on the recent works of Nie \(et \; al.\) [13] and Khattar and Gidney [10] on the technique of conditionally clean ancillae. By combining these two key elements, we present a novel approach to design quantum adders that can perform the addition of two n-bit numbers in depth \(O\left( \log ^2 n \right) \) without the use of any ancilla and using classical reversible logic only (Toffoli, \(\textsf{CNOT}\) and \(\textsf{X}\) gates).