Abstract

The Linear Combination of Unitaries (LCU) method is a powerful scheme for the block encoding of operators but suffers from high overheads. In this work, we discuss the parallelisation of LCU based on partitioning of observables into groups, as well as the use of adaptive circuits that allow us to perform required Clifford circuits in constant depth. This parallelisation only requires a modest increase in the number of qubits in order to produce an O(n) depth reduction. Our method can significantly reduce the overall space-time volume of the computation, even when including the increase in magic state factories required by parallelisation [1].

[1] G. Boyd, Low-Overhead Parallelisation of LCU via Commuting Operators, arXiv: 2312.00696 (2024)