Polylogarithmic-depth controlled-NOT gates without ancilla qubits

In quantum computing, multi-control NOT gates are the quantum equivalent of classical ‘AND’ operations. While being true building blocks of quantum algorithms, their decomposition into native quantum gates is non-trivial. We achieve exponentially shorter circuits than previous state-of-the-art.
Published in Physics and Computational Sciences
Polylogarithmic-depth controlled-NOT gates without ancilla qubits
Like

Share this post

Choose a social network to share with, or copy the URL to share elsewhere

This is a representation of how your post may appear on social media. The actual post will vary between social networks

Like modern industrial sectors, the drug development industry demands ever-increasing computing power. A promising solution to this challenge leverages the principles of quantum physics to perform expensive computations with quantum processor units (QPUs). In that context, quantum algorithms show potential for a dramatic acceleration over classical methods on specific problems, such as the simulation of molecules and materials. Nonetheless, quantum computing is still in its early stages, the hardware is noisy, and software is still too demanding to accomplish.As an interdisciplinary team of physicists, mathematicians, and chemists with an early focus on quantum algorithms, our research in the field has two primary objectives:

  1. devising innovative quantum algorithms to solve the many-body problem, leveraging our background in traditional theoretical physics and chemistry, and
  2. improving fundamental quantum algorithm subroutines, for example at the quantum circuit decomposition level. This step is typically encountered when we implement our algorithms on quantum emulators to conduct simulations and solve proof-of-principle systems.

Only in these situations do we focus on efficiently breaking down oracles (i.e. a black-box operation that is used as input to another algorithm) into single- and two-qubit gates, occasionally encountering unexpected obstacles or discovering new ideas for improving circuit decompositions. In our opinion, this underscores how important it is to considering the end-to-end resolution of the problem, even though it involves performing simple simulations of quantum circuits on classical devices. Multi-control NOT gates are the quantum equivalent of ‘AND’ operations. While being true building blocks of many quantum algorithms, their decomposition into native quantum gates is non-trivial. Our paper "Polylogarithmic-depth controlled-NOT gates without ancilla qubits" achieves  exponentially shorter circuits than previous state-of-the-art. To perform the multi-controlled operation, we divide the quantum register into quadratically smaller registers and perform controls in parallel to minimise the circuit depth. As this process can be carried out using a single borrowed ancilla qubit, we show it can be repeated recursively, applying similar factorisation and parallel control to each of the smaller registers. This recursive approach results in an overall efficient quantum circuit with polylogarithmic depth. Three distinct decompositions are presented:

  • an exact one using one borrowed ancilla with a circuit depth Θ(log(n)3),
  • an approximating one without ancilla qubits with a circuit depth O(log(n)3log(1/ε) ,
  • an exact one with an adjustable-depth circuit which decreases with the number m ≤ n of ancilla qubits available as O(log(2n/m)3+log(m/2)).

The ideas developed in this paper suggest a scope towards more efficient quantum circuits. As quantum computing continues to push boundaries, it paves the way towards exciting opportunities for addressing complex computational problems across various fields, including drug design, finance, machine learning, and energy. This area of work could be leveraged to improve the challenging task of designing quantum compilers. Regarding us, we resume our quest of quantum algorithm development for the many-body problem and other partial differential equations, staying alert to potential enhancements in quantum circuits we may incorporate or develop along the way.

Please sign in or register for FREE

If you are a registered user on Research Communities by Springer Nature, please sign in

Follow the Topic

Quantum Computing
Mathematics and Computing > Computer Science > Theory of Computation > Models of Computation > Quantum Computing
Quantum Physics
Physical Sciences > Physics and Astronomy > Quantum Physics
Quantum Information
Physical Sciences > Physics and Astronomy > Quantum Physics > Quantum Information

Related Collections

With collections, you can get published faster and increase your visibility.

Biology of rare genetic disorders

This cross-journal Collection between Nature Communications, Communications Biology, npj Genomic Medicine and Scientific Reports brings together research articles that provide new insights into the biology of rare genetic disorders, also known as Mendelian or monogenic disorders.

Publishing Model: Open Access

Deadline: Jan 31, 2025

Carbon dioxide removal, capture and storage

In this cross-journal Collection, we bring together studies that address novel and existing carbon dioxide removal and carbon capture and storage methods and their potential for up-scaling, including critical questions of timing, location, and cost. We also welcome articles on methodologies that measure and verify the climate and environmental impact and explore public perceptions.

Publishing Model: Open Access

Deadline: Mar 22, 2025