Accelerating ground state calculation using
probabilistic imaginary-time evolution and quantum amplitude amplification
Hirofumi Nishi1,2, Taichi Kosugi1,2, Yusuke Nishiya1,2, and Yu-Ichiro Matsushita1,2,3
1 Tokyo Institute of Technology
2 Quemix Inc.
See also Contributed talk [C06-1-03]
3 National Institute for Quantum Science and Technology
2:20PM - 2:40PM Sun. Arg. 6 301 (3F)

Background
Application of the PITE method:
Exhaustive search among all candidate geometries

Ground state preparation
Quantum Phase Estimation (QPE):
A standard algorithm for estimating the ground-state energy.
The computational cost of QPE depends on the initial state,
which scales as O(1/(c1|2 ε)).

Aim of this study(1) Investigate the computational cost of the PITE method

Ar atom above a benzene molecule

Ground state preparation is classified as complexity-classquantum Merlin-Arthur (analogy of complexity-class NP
on a quantum computer). Exponential computational costis required in the PITE method.

After 19th step of PITE, the moststable geometry has the highest
probability|c1|2: the probability weight of the ground state in the initialstate, ε: a statistical errorPotential energy surface (Top view)(2) Realize quantum acceleration in ground state preparation

Interaction energy

Imaginary-time evolution (ITE) operator on a quantum
computer is one promising way for ground state preparation.
The ITE operator is probabilistically realized on a quantum
computer (PITE method), comprising single ancilla qubit andforward- and backward-controlled real time evolution (RTE).

Ground state is probabilistically obtained in the PITE
method. Combining quantum amplitude amplification isremedy for probabilistic nature, which also bring us
quantum acceleration.

Optimal position of Ar
Candidate
T. Kosugi, H. Nishi, and Y.-i. Matsushita, arXiv:2210.09883 (2022).

T. Kosugi et al, Phys. Rev. Res., 4(3) 033121(2022).

Probabilistic Imaginary-Time Evolution and Quantum Amplitude Amplification
Exact PITE

|0i|0>

HH W W

Embed the nonunitary as a submatrix into⌦n⊗n| |ψi > /a unitary•

Rz

Success state(Target state)†-iκΘ
URTE iκΘ URTEe

Quantum Amplitude Amplification (QAA)

WW††

e

Initial state
1st step QAA
success state

ancilla bit

Reflection

m timesQAA steps

aa

Initial state

Success state: probabilistically obtained>

Approximated PITE

|0i|0H
H

Amplified state after m steps of QAA•WWThe arccos function is expanded⌦n⊗n||ψi/up to the first order of Δτ

>

failure state

RRzz

Failure state(Orthogonal state)W††W

oracle
aa

UURTE

RTE

†
†
U
URTE
RTE

Optimal number of repetitions of QAA:

Brassard, Gilles, et al. "Quantum amplitude amplification and estimation." Contemporary Mathematics 305, 53 (2002)

Feature: Express ITE operator with RTE operators
After K operations of the approximated PITE, observing all ancilla state as |0> state leads
to collapse from the entangled state to

Quantum circuit for QAA combined with multistep PITE
Quantum circuit for the amplitude amplification operator of the PITE method
Forward- and backward- controlled RTE gates

The normalization constant(Total success probability):

W

Rz†

W†

H

H

W

Rz

W†

W

Rz†

W†

H

H

W

Rz

W†

S0

Total success probability: when the FK is well design to decay unwanted stateW†

Rz†

HS0H…

W…

…

Computational cost…

…

Approximated ITE operator

…

WRzW†

⊗nV†RTE

Every quantum algorithm that decays unwanted
state by non-unitary operation shows same scaling

V†RTE

V†RTE

Uref †Uref= 𝒰 " PITE+ref

Computational cost for PITE:

V RTE

V RTE

V RTE

= 𝒰PITE+ref

Computational cost for PITE combined with QAA (multi-step PITE)

If we do not know even the approximated ground state at all, e.g., |c1|=1/N, the computational
cost of at least one success scales as O(N). No quantum acceleration.
H. Nishi, K. Hamada, Y. Nishiya, T. Kosugi, and Y.-i. Matsushita, arXiv:2305.04600 (2023).

Quadratic speedup owing to combining QAA
H. Nishi, Y. Nishiya, T. Kosugi, and Y.-i. Matsushita, in preparation.

Result: Numerical Simulations
Setup
The Heisenberg model
Exponential
speedup for δ

Quadratic speedup
for |c1|<j,k> represents the combination of the nearest neighbors of theclosed one-dimensional chain.
Random magnetic field hj are randomly chosen from uniform
distribution as hj∈[-1, 1].

The controlled RTE gate is implemented by the fourth-order TrotterSuzuki decomposition for even-odd group of the Hamiltonian.

Quadratic speedup
for |c1|

Exponentialspeedup for δThe initial state is uniform probability weights of each eigenvector:|ci|2=1/N

Computational cost was estimated when the infidelity was below δ=10-4.
QAA is efficient for |c1|<1/2 due to overhead of QAA.

Conclusion
1. Investigated the computational cost of the PITE method that implements a nonunitary ITE operator on a quantum computer with a single ancilla qubit.
2. Proposed a quantum algorithm combining QAA with PITE for ground-state preparation that present quadratic speedup overt he classical one.