Southwest Quantum Information and Technology

Improved quantum algorithms using linear combination of unitaries

Presenting Author: Anirban Narayan Chowdhury, University of New Mexico CQuIC
Contributing Author(s): Yigit Subasi, Rolando Diego Somma

The technique of implementing a linear combination of unitary (LCU) operators has led to significant improvements in the complexities of quantum algorithms for diverse problems such as Hamiltonian simulation and solving linear systems of equations. Here we combine LCU with a version of amplitude amplification to tackle two tasks that arise in the context of quantum algorithms for optimization problems - namely Gibbs state preparation, and that of implementing a reflection about eigenstates of a unitary operator. In both cases, we obtain improvements in resource requirements over earlier protocols that used quantum phase estimation (PE). The LCU approach for Gibbs state preparation has complexity that scales exponentially better in inverse precision and, for a certain class of Hamiltonians, polynomially better in terms of other parameters. We use similar ideas to approximate a reflection about an eigenstate of a given unitary using an LCU. Our implementation requires exponentially fewer ancilla qubits in terms of a precision parameter than a PE based approach, and has gate complexity that is comparable. Our analysis also improves upon the gate complexity of the PE-reflection by using an approximate quantum Fourier transform. Our results are useful as they reduce the resources needed by a large variety of existing quantum algorithms. We also prove a lower bound on the query complexity of implementing reflections.

(Session 9c : Friday from 4:15pm-4:45pm)