Tradeoffs between quantum and classical resources in linear combination of unitaries
Authors
Kaito Wada
Hiroyuki Harada
Yasunari Suzuki
Yuuki Tokunaga
Naoki Yamamoto
Suguru Endo
Abstract
The linear combination of unitaries (LCU) algorithm is a building block of many quantum algorithms. However, because LCU generally requires an ancillary system and complex controlled unitary operators, it is not regarded as a hardware-efficient routine. Recently, a randomized LCU implementation with many applications to early FTQC algorithms has been proposed that computes the same expectation values as the original LCU algorithm using a shallower quantum circuit with a single ancilla qubit, at the cost of a quadratically larger sampling overhead. In this work, we propose a quantum algorithm intermediate between the original and randomized LCU that manages the tradeoff between sampling cost and the circuit size. Our algorithm divides the set of unitary operators into several groups and then randomly samples LCU circuits from these groups to evaluate the target expectation value. Notably, we analytically prove an underlying monotonicity: larger group sizes entail smaller sampling overhead, by introducing a quantity called the reduction factor, which determines the sampling overhead across all grouping strategies. Our hybrid algorithm not only enables substantial reductions in circuit depth and ancilla-qubit usage while nearly maintaining the sampling overhead of LCU-based non-Hermitian dynamics simulators, but also achieves intermediate scaling between virtual and coherent quantum linear system solvers. It further provides a virtual ground-state preparation scheme that requires only a resettable single-ancilla qubit and asymptotically shows advantages in both virtual and coherent LCU methods. Finally, by viewing quantum error detection as an LCU process, our approach clarifies when conventional and virtual detection should be applied selectively, thereby balancing sampling and hardware overhead.
