TETRIS-ADAPT-VQE: An adaptive algorithm that yields shallower, denser circuit ans\"atze

Adaptive quantum variational algorithms are particularly promising for simulating strongly correlated systems on near-term quantum hardware, but they are not yet viable due, in large part, to the severe coherence time limitations on current devices. In this work, we introduce an algorithm called TETRIS-ADAPT-VQE, which iteratively builds up variational ans\"atze a few operators at a time in a way dictated by the problem being simulated. This algorithm is a modified version of the ADAPT-VQE algorithm in which the one-operator-at-a-time rule is lifted to allow for the addition of multiple operators with disjoint supports in each iteration. TETRIS-ADAPT-VQE results in denser but significantly shallower circuits, without increasing the number of CNOT gates or variational parameters. Its advantage over the original algorithm in terms of circuit depths increases with the system size. Moreover, the expensive step of measuring the energy gradient with respect to each candidate unitary at each iteration is performed only a fraction of the time compared to ADAPT-VQE. These improvements bring us closer to the goal of demonstrating a practical quantum advantage on quantum hardware.