Making a Workhorse Quantum Algorithm Fit Near-Term Devices 

Many of the most powerful quantum algorithms rely on a single “workhorse” subroutine called the linear combination of unitaries (LCU). This recipe lets a quantum computer carry out very general transformations, and it underpins leading methods for simulating quantum systems, estimating ground-state energies of materials, solving systems of linear equations, and designing quantum walks used for search. But the standard way to run LCU needs many extra “helper” (ancilla) qubits and intricate multi-qubit control, so it really only fits giant, fully error-corrected machines that are still far in the future.

In this work, we show how to make LCU practical on the more modest quantum devices we are likely to see first. We introduce three new implementations. Single-ancilla LCU uses just one helper qubit and short circuits repeated many times. Analog LCU realizes LCU by naturally coupling qubits to a simple continuous system, such as a harmonic oscillator. Ancilla-free LCU proves that for some important tasks, such as quantum-walk–based search, ancilla qubits can be removed entirely.

We apply these methods to concrete problems in ground-state property estimation, Hamiltonian simulation, quantum linear systems, and quantum walks, showing how a central theoretical tool can be reshaped for realistic near-term quantum hardware.