A constant quantum depth may be enough for Boolean logic

Christopher Kang and colleagues have demonstrated that any Boolean arithmetic circuit can be implemented on a quantum computer with constant quantum depth and constant reaction depth, despite requiring exponential space and leaving qubits in a “dirty” state. The research formalizes the concept of reaction depth, the number of times a quantum program must consult a classical computer, and reveals a relationship between a unitary’s magic depth and its reaction depth after compilation.

This work uses a specific gateset of homogeneous Z- and X-type Pauli Product Measurements and Toffoli states to achieve this speedup for certain quantum algorithms. The team also implemented two efficient AutoAND circuits with only a Toffoli state and the same homogeneous PPMs.

Formalizing Reaction Depth for Quantum Circuit Analysis

The team’s analysis highlights the distinction between a circuit’s reaction depth and that of a specific circuit run; the “magic depth” of a unitary, a measure of its non-Clifford character, can exceed the reaction depth following compilation into Clifford computation and magic state injection. The researchers also focused on implementations of the quantum ripple-carry adder and quantum schoolbook multiplier, achieving competitive performance with existing methods despite the limitations of their chosen gateset.

The authors state in their paper that reducing runtimes of quantum applications is critical for practical viability, emphasizing the importance of minimizing the need for classical coprocessor intervention during quantum computations. This work’s focus on coherent Boolean logic, a frequently used but computationally expensive element in quantum algorithms, suggests a pathway toward optimizing performance in a range of applications, even if full scalability remains a challenge.

👉 More information
🗞 On Reaction Depth and Fast Fault-Tolerant Boolean Logic
✍️ Christopher Kang, Alexander Cowtan, Adam Bene Watts, Guillaume Dauphinais and Benjamin Ide
🧠 ArXiv: https://arxiv.org/abs/2611.24687v1

Stay current

See today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals.

Avatar of Ivy Delaney

Ivy Delaney

Ivy Delaney has been working with neural networks and machine learning since the mid-nineties, back when a couple of hidden layers and a long afternoon of training counted as ambitious. She has watched the field go from academic curiosity to the thing quietly running underneath everything, and she brings that long view to quantum computing. For Quantum Zeitgeist she covers the ground where the two fields meet. That means quantum machine learning and the variational algorithms it leans on, and it also means the less glamorous but more interesting story of classical machine learning already doing real work inside quantum machines, decoding error-correcting codes, calibrating noisy hardware and learning the error models that simulators depend on. She writes about the hardware those algorithms have to run on too, and about the post-quantum cryptography scramble that the same hardware has set off. Her stories typically start with the paper, whether that is peer-reviewed work, conference proceedings or an arXiv preprint, with the source linked so you can hold a claim up against the research it came from. She is unimpressed by benchmarks that will not say what they beat, and by demonstrations that only work in the press release.

Latest Posts by Ivy Delaney: