Ground state preparation and energy estimation on early fault-tolerant
  quantum computers via quantum eigenvalue transformation of unitary matrices
Under suitable assumptions, the algorithms in [Lin, Tong, Quantum 2020] 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, whose implementation is known to
require a large resource overhead. We develop a tool called quantum eigenvalue
transformation of unitary matrices with real polynomials (QET-U), which uses a
controlled Hamiltonian evolution as the input model, a single ancilla qubit and
no multi-qubit 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 anti-commutation relations and
further removes the need of implementing the controlled Hamiltonian evolution.
Coupled with 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 multi-qubit
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 estimating using a constant
number of ancilla qubits (no more than 3).
Yulong Dong Lin Lin Yu Tong