  A key challenge in realizing fault-tolerant quantum computers is circuit
optimization. Focusing on the most expensive gates in fault-tolerant quantum
computation (namely, the T gates), we address the problem of T-count
optimization, i.e., minimizing the number of T gates that are needed to
implement a given circuit. To achieve this, we develop AlphaTensor-Quantum, a
method based on deep reinforcement learning that exploits the relationship
between optimizing T-count and tensor decomposition. Unlike existing methods
for T-count optimization, AlphaTensor-Quantum can incorporate domain-specific
knowledge about quantum computation and leverage gadgets, which significantly
reduces the T-count of the optimized circuits. AlphaTensor-Quantum outperforms
the existing methods for T-count optimization on a set of arithmetic benchmarks
(even when compared without making use of gadgets). Remarkably, it discovers an
efficient algorithm akin to Karatsuba's method for multiplication in finite
fields. AlphaTensor-Quantum also finds the best human-designed solutions for
relevant arithmetic computations used in Shor's algorithm and for quantum
chemistry simulation, thus demonstrating it can save hundreds of hours of
research by optimizing relevant quantum circuits in a fully automated way.
