Polylogarithmic-depth controlled-NOT gates without ancilla qubits.

Controlled operations are fundamental building blocks of quantum algorithms. Decomposing n-control-NOT gates (Cn(X)) into arbitrary single-qubit and CNOT gates, is a crucial but non-trivial task. This study introduces Cn(X) circuits outperforming previous methods in the asymptotic and non-asymptotic regimes. 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 ) 3 log ( 1 / ϵ ) ) and an exact one with an adjustable-depth circuit which decreases with the number m≤n of ancilla qubits available as O ( log ( n / ⌊ m / 2 ⌋ ) 3 + log ( ⌊ m / 2 ⌋ ) ) . The resulting exponential speedup is likely to have a substantial impact on fault-tolerant quantum computing by improving the complexities of countless quantum algorithms with applications ranging from quantum chemistry to physics, finance and quantum machine learning.

Sparse Quantum State Preparation for Strongly Correlated Systems.

Quantum computing allows, in principle, the encoding of the exponentially scaling many-electron wave function onto a linearly scaling qubit register, offering a promising solution to overcome the limitations of traditional quantum chemistry methods. An essential requirement for ground state quantum algorithms to be practical is the initialization of the qubits to a high-quality approximation of the sought-after ground state. Quantum state preparation enables the generation of approximate eigenstates derived from classical computations but is frequently treated as an oracle in quantum information. In this study, we investigate the quantum state preparation of prototypical strongly correlated systems' ground state, up to 28 qubits, using the Hyperion-1 GPU-accelerated state-vector emulator. Various variational and nonvariational methods are compared in terms of their circuit depth and classical complexity. Our results indicate that the recently developed Overlap-ADAPT-VQE algorithm offers the most advantageous performance for near-term applications.