Ground-State Preparation and Energy Estimation on Early Fault-Tolerant Quantum Computers via Quantum Eigenvalue Transformation of Unitary Matrices

Under suitable assumptions, some recently developed quantum algorithms can estimate the ground-state energy and prepare the ground state of a quantum Hamiltonian with near-optimal query complexities. However, this is based on a block-encoding input model of the Hamiltonian, the implementation of which is known to require a large resource overhead. We develop a tool called quantum eigenvalue transforma-tion of unitary matrices with real polynomials (QETU), which uses a controlled Hamiltonian evolution as the input model, a single ancilla qubit, and no multiqubit control operations and is thus suitable for early fault-tolerant quantum devices. This leads to a simple quantum algorithm that outperforms all pre-vious algorithms with a comparable circuit structure for estimating the ground-state energy. For a class of quantum spin Hamiltonians, we propose a new method that exploits certain anticommutation relations and further removes the need to implement the controlled Hamiltonian evolution. Coupled with a Trotter-based approximation of the Hamiltonian evolution, the resulting algorithm can be very suitable for early fault-tolerant quantum devices. We demonstrate the performance of the algorithm using IBM QISKIT for the transverse-field Ising model. If we are further allowed to use multiqubit Toffoli gates, we can then implement amplitude amplification and a new binary amplitude-estimation algorithm, which increases the circuit depth but decreases the total query complexity. The resulting algorithm saturates the near-optimal complexity for ground-state preparation and energy estimation using a constant number of ancilla qubits (no more than three).

Automated summary

This paper introduces a tool called QETU, which utilizes controlled Hamiltonian evolution and a single ancilla qubit to optimize the query complexities of quantum algorithms. A new method is proposed to further improve the performance of the algorithm by exploiting specific anticommutation relations for a class of quantum spin Hamiltonians. The algorithm demonstrates promising performance in early fault-tolerant quantum devices and can be further optimized using multiqubit Toffoli gates.