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:
devising innovative quantum algorithms to solve the many-body problem, leveraging our background in traditional theoretical physics and chemistry, and
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.