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 transformation 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 previous 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).
