Implementing Linear Combination of Unitaries on Intermediate-term Quantum Computers

Over the years, the framework of Linear combination of unitaries (LCU) has been extremely useful for designing a plethora of quantum algorithms. In this work, we explore whether this widely applicable paradigm can be implemented on quantum computers that will be available immediately after the current NISQ stage. To this end, we develop three variants of LCU and apply each, to quantum algorithms of practical interest. First, we develop a physically motivated, continuous-time analogue of LCU (``Analog LCU''). This technique, implementable on hybrid qubit-qumode systems, is simpler than its discrete-time counterpart. We use this method to develop analog quantum algorithms for ground state preparation and quantum linear systems. We also develop a randomized quantum algorithm to sample from functions of Hamiltonians applied to quantum states (``Single-Ancilla LCU''). This approach repeatedly samples from a short-depth quantum circuit and uses only a single ancilla qubit. We use this to estimate expectation values of observables in the ground states of a Hamiltonian, and in the solution of quantum linear systems. This method is suitable for early fault-tolerant quantum computers. Our third approach stems from the observation that for several applications, it suffices to replace LCU with randomized sampling of unitaries according to the distribution of the LCU coefficients (``Ancilla-free LCU''). This is particularly useful when one is interested in the projection of a quantum state implemented by an LCU procedure in some subspace of interest. We demonstrate that this technique applies to the spatial search problem and helps establish a relationship between discrete and continuous-time quantum walks with their classical counterparts. Our work demonstrates that generic quantum algorithmic paradigms, such as LCU, can potentially be implemented on intermediate-term quantum devices.