A Generalized Circuit for the Hamiltonian Dynamics Through the Truncated Series
Ammar Daskin
Department of Computer Engineering, Istanbul Medeniyet University, Uskudar, Istanbul, Turkey

Sabre Kais

arXiv:1801.09720v1 [quant-ph] 29 Jan 2018

Department of Chemistry, Department of Physics and Birck
Nanotechnology Center, Purdue University, West Lafayette, IN, USA
In this paper, we present a fixed-quantum circuit design for the simulation of the Hamiltonian
dynamics, H(t), through the truncated Taylor series method described by Berry et al. [1]. In
particular, Hamiltonians which are not given as sums of unitary matrices but given as general
matrices are considered and a simple divide and conquer method is presented for mapping the
Hamiltonians into the circuit. The circuit is general and can be used to simulate any given matrix in
the phase estimation algorithm by only changing the angle values of the quantum gates implementing
the time variable t in the series. We analyze the circuit complexity and show that it requires O(N 2 )
number of CN OT gates for dense matrices, where N is the matrix size. We finally discuss how
it can be used in adaptive processes and eigenvalue related problems along with a slight modified
version of the iterative phase estimation algorithm.

I.

INTRODUCTION

Since the standard quantum computing requires any operation to be a unitary transformation in the Hilbert space,
quantum algorithms in general deal with the problems represented by unitary matrices. One of these algorithms is
the phase estimation[2] used in the eigenvalue related problems. Given an estimate of the eigenvector, the algorithm
finds the associated eigenvalue of a unitary matrix. In particular, it estimates the value of φ in the eigenvalue eiφ
when given an estimate of the associated eigenvector |ϕi. If U is the time evolution operator of a Hamiltonian, i.e.
U = eiHt , the algorithm also yields the eigenvalue of the Hamiltonian H. Therefore, for the simulation of a quantum
system on quantum computers; it is necessary to have its time evolution operator as a quantum circuit. A very
common approach to estimate eiHt follows the generalized Trotter formula [3, 4] in which a mixed product of the
exponential of smaller terms forming the Hamiltonian operator is taken as an approximation. This product accurately
yields the evolution if all terms forming the Hamiltonian commute. Otherwise, an error bounded by the order of the
approximation is involved [5].
Berry et al.[1] have proposed using the Taylor expansion of eiHt
√ directly on quantum circuits by adding an ancillary
register to the system. In Ref.[6], we have showed that when I − H2 is available and H is Hermitian, one can use
the following unitary matrix in the phase estimation algorithm:
!
√
2
H
−
I
−
H
√
.
(1)
I − H2
H
This notion of using an extended system to simulate a small one is generalized as quantum signal processing [7], where
a unitary matrix similar to the one in Eq.(1) used without the phase estimation algorithm. Recently, the overhead
of the truncated Taylor series method is reduced by showing how
 to efficiently get the square root of matrix in a
different basis [8]. In Ref.[9], successive applications of I + iH/µ with µ ≥ 10||H|| are used to obtain the eigenvalue
of H from the sinus value of the phase in the phase estimation algorithm. All of these approaches are assumed that
the Hamiltonian is given as a sum of simple unitary matrices. In Ref.[10], the truncated Taylor series method is used
for quantum simulations after decomposing the configuration interaction matrix into a sum of sparse matrices.
In this paper, we present a general
design 
for the matrices not given as sums of unitary matrices by
 circuit
√
employing the Taylor expansion of tH + i I − t2 H2 truncated at the third term. The circuit can be used in
the phase estimation algorithm by only changing the part implementing the coefficients related to time step t. The
eigenvalue of H can be obtained from the cosine value of the phase. We show that the whole circuit requires O(N 2 )
number of CNOT gates for the dense matrices when it is used in the phase estimation algorithm. This complexity
can be further reduced in the case of sparse matrices since the number of gates used in the circuit solely depends on
the matrix elements.
The remaining part of this paper is organized as follows: In the following subsection, we describe the truncated
Taylor series method. Then in the next section, the Taylor expansion used in this paper is described. Then, we

II

THE SERIES USED FOR THE CIRCUIT

explain the divide and conquer method used to obtain the circuit. After analyzing the complexity of the circuit in
terms of the number of CNOTs, we discuss how the method can be used with special matrices and in the adaptive
processes along with the modified iterative phase estimation algorithm.
A.

Truncated Taylor Series Method

For a matrix U , one can build the following by using an ancilla quantum register:


Ū •
U=
,
• •

(2)

where “•” represents matrices which have no special meaning. For any arbitrary |ψi on the system register, the above
matrix generates the following output state in the standard basis:
U |0i |ψi = √

1
1
|Φi + √ |0i Ū |ψi .
1 − P0
P0

(3)

Here, |Φi represents the part of the output in which the first register is not |0i. And obviously when the first register
in |0i state, the output yields Ū |ψi with probability ||Ū |ψi ||2 /P0 . Therefore, U can be used to emulate the action of
U on any arbitrary state |ψi. This idea is used in various contexts: e.g., in Ref.[11], a programmable circuit design is
PL
presented for unitary matrices. Given a Hamiltonian H = k αk Hk with Hk representing a unitary matrix; through
the Taylor expansion of eiHt truncated at the Kth term, Berry et al.[1] have showed:
U (t) = eiHt ≈ Ū (t) =

K
j
X
(iHt)
j=0

j!

=

M
X

βj V j ,

(4)

j=0

where M = LK . And while Vj s are some products of Hk s, βj s are products of αk s. Furthermore, they have showed
that the above expansion can be implemented as a circuit by using the following:



Ū •
∗
U = B ⊗ I V (B ⊗ I) =
.
(5)
• •
PM −1 p
where V = blkdiag (V 1, V 2, . . . , VM ) and B =
βj |ji. V can be implemented as a circuit by using an
j
additional logM qubits and controlling each Vj with the |jith state of these qubits. Here, when Ū is sufficiently
close to a unitary matrix, one P
can also maximize the probability P0 by using the oblivious amplitude amplification
algorithm. In that case, when j βj = 2, the amplification requires only one iteration.
II.

THE SERIES USED FOR THE CIRCUIT

If the Taylor expansion is truncated at the third term;
eiHt ≈ I + itH −

t2 H 2
.
2

(6)

When ||tH|| ≤ 1; instead of using Taylor expansion for eitH , the following can be used to deal with the spectra of the
Hamiltonian (similar ones used in prior arts Ref.[10, 12–14]):
p
U (t) = tH + i I − t2 H2 .
(7)
Here, U (t) describes a unitary matrix [15] with the eigenvalues whose real parts are equal to those of the Hamiltonian.
In addition, U (t) and tH have the same eigenvectors. Eq.(6) also is an approximation to iU (t). Because, if we use
the Taylor expansion of the square root;
!
t2 H 2
U (t) ≈ Ū (t) = tH + i I −
.
(8)
2
The most significant part of this approximation is that it does not introduce any error on the real part of the eigenvalues
of U (t) given in Eq.(7). Hence, using the phase estimation algorithm, one can obtain the eigenvalue from the cosine
value of the phase. In the following section, a circuit design is presented for Ū (t) given in Eq.(8).
2

A

Divide and Conquer Method

III
III.

CIRCUIT IMPLEMENTATION OF U (t)

CIRCUIT IMPLEMENTATION OF U (t)

When H is given as a sum of unitary matrices or matrices which can be easily mapped to quantum gates, then
one can design the circuit for U (t) by following Eq.(4) where the summation is converted into a product formula
or the standard Trotter-Suzuki decomposition. This is the case for molecular Hamiltonians given in the second
quantization[16, 17].
However, if H is not given as a sum of simple1 unitaries, then the following divide an conquer method can be used
to rewrite the Hamiltonian as a sum of unitary matrices:
i) The matrix is first recursively divided into submatrices.
ii) Then, each submatrix is mapped to a quantum gate.
iii) Using a coefficient matrix BH , the Hamiltonian is generated as a part of the following matrix:


H •
UH =
.
• •
iv) Finally, UH is employed to obtain Ū (t) in Eq.(8) as a part of the following matrix:


Ū (t) •
.
U (t) =
• •

(9)

(10)

The details are given in the following subsections:

A.

Divide and Conquer Method

First, a given Hamiltonian H ∈ RN with (N = 2n ) is divided into four blocks:

 
 

A0 A1
A0
A1
H=
=
+
.
A2 A3
A3
A2

(11)

Using the vectors in the standard basis, this can be rewritten as:

H = |0i h0| A0 + |1i h1| A3 + |0i h1| A1 + |1i h0| A2


 
= |0i h0| A0 + |1i h1| A3 + X ⊗ IN/2 |0i h0| A1 + |1i h1| A2 ,
where IN/2 describes an N/2 dimensional identity matrix and


0 1
X=
.
1 0

(12)

(13)

This division into blocks is recursively continued until each block dimension becomes 2 or circuit representations of
the blocks become known. For instance, after the second recursion step, we have the following (please see Appendix
A 1 and A 2 for the mathematical steps and the third recursion):

H = |00i h00| A00 + |01i h01| A03 + |10i h10| A30 + |11i h11| A33



+ I ⊗ X ⊗ IN/4 |00i h00| A01 + |01i h01| A02 + |10i h10| A31 + |11i h11| A32



+ X ⊗ I ⊗ IN/4 |00i h00| A10 + |01i h01| A13 + |10i h10| A20 + |11i h11| A23



+ X ⊗ X ⊗ IN/4 |00i h00| A11 + |01i h01| A12 + |10i h10| A21 + |11i h11| A22 .

1

simple in the sense that the unitary matrix can be implemented by using a few quantum gates.

3

(14)

B

Generating Circuit for UH in Eq.(9)

III

CIRCUIT IMPLEMENTATION OF U (t)

In matrix form,

A
 00
A02
H=
 A20
A22

 
A01
A10
A03  A12
A21
A30
A23
A32


A11

A13 
.
A31 
A33

(15)

Note that following the subscripts of A[... ] s from left to right one can easily find the matrix elements for any A[... ] .
After any kth recursive step, the Hamiltonian can be written more concisely in the following form:
H=

k
2X
−1



Vj Pj (X, I) ⊗ IN/2k .

(16)

j=0

Here, Pj (X, I) is a permutation matrix constructed by using the tensor product of X and identity matrices, i.e.:
Pj (X, I) =

k−1
O

X ji , with j = (j0 . . . jk−1 )2 .

(17)

i=0

Each Vj describes a multi controlled network: in matrix form, a block diagonal matrix where some A[... ] s are tiled on
its diagonal. To find which A[... ] s in step k are involved in any of Vj s, we start from V0 and place all possible words
wi with length k from the alphabet {0, 3} as the subscript of Awi , i.e.:
V0 =

k
2X
−1

|ii hi| Awi ,

(18)

i=0

Here, |ii is the ith vector in the standard basis and wi represents the ith word in the set. The subscripts of A[... ] s in
each Vj can be determined from V0 and Pj (X, I) as follows:
• if there is an X on the ith qubit, then we make the following change in the subscripts of A[... ] s in V0 :
– (3 → 2), if the ith letter of the subscript is 3, we make it 2.
– (0 → 1), if the ith letter is 0, we make it 1.
– no change necessary for the other letters.
You can consider this as if we apply X gate to the subscript and switch 3s into 2s and 0s into 1s.
B.

Generating Circuit for UH in Eq.(9)

Each Vj describes a multi controlled network: There are N/2 number of A[... ] s for each Vj . Once the involved A[... ] s
are determined, they can be mapped to a circuit by using different control bit schemes for each A[... ] . Note that each
A[... ] can be written as a sum of two unitary matrices. For instance,




q
q
1
1
2
2
A[... ] + i I − A[... ] +
A[... ] − i I − A[... ]
(19)
A[... ] =
2
2
This will double the number of Vj s. Since the matrix elements of A[... ] are real, it can be also described as a sum of
three rotations about the y-axis, which triples the number of terms:


a a
A[... ] = 00 01
a10 a11






(20)
1 − (a00 + a11 ) (a10 − a01 )
1 (a00 + a11 ) − (a10 − a01 )
a
a01
= 00
+
+
.
a01 −a00
2 (a10 − a01 ) (a00 + a11 )
2 (a10 − a01 ) (a00 + a11 )
Then, the circuits for Vj s are combined in select (V ) by using an ancilla register: select (V ) applies Vj when the
ancilla is in |ji state. The matrix form of this operation is as follows:


V0


V1


V =
(21)
.
.
.


.
VN/2
4

B

Generating Circuit for UH in Eq.(9)

IV

TOTAL GATE AND QUBIT COUNT

FIG. 1: The circuit for UH for any 8 × 8 Hamiltonian matrix. Here, since there is no coefficient on any A[... ] , BH
can be considered as a tensor product of two Hadamard gates. Also note that permutation matrices are simplified
into two CNOTs in the end.

FIG. 2: The circuit for U (t). In total (2n + 1) qubits are involved
 B is a 4 × 4 unitary matrix with
√ in the√circuit.
t, 1, t/ 2, 0 .
the leading row and column

Furthermore, using the same control scheme, select (P ) is constructed for the permutation matrices:


P0


P1


(22)
V =
.
.
..


PN/2

∗
The circuit for UH implementing the Hamiltonian then becomes
 the product BH ⊗ I V P (BH ⊗ I), where BH forms
a state with the square root of the coefficients of Vj Pj (X, I) s. An example UH for a general 8 × 8 Hamiltonian is
presented in Fig.1, where Pj s are simplified into two CNOT gates.
C.

Combining All for Ū (t)

To implement U (t), we will employ the following selection matrix:


UH


iI
.
V=


UH2
•
Then, U (t) is generated by using two more qubits and the matrix B which implements the coefficients:
V is generated with the help of a permutation matrix also used in Ref.[9]:


IN
.
X ⊗ I3N
Π=
IN

(23)
√

√ 
t, 1, t/ 2, 0 .

(24)

The resulting circuit is shown in Fig.2.
IV.

TOTAL GATE AND QUBIT COUNT

The total complexity of the whole circuit given in Fig.2 is governed by the number of gates, in particular CNOTs
used to implement UH . The complexity of UH is determined by the number of Vj s. We can determine the number of
5

B

Adaptive Processes

V

DISCUSSION AND FUTURE WORK

qubits and CNOTs by counting the number of A[... ]. In the final step of the recursive division, the matrix elements are
put into group of four elements. This yields N 2 /4  number of A[... ] s. If each A[... ] is written as a sum of two unitary
2
matrices,
 then the number of gates becomes N /2 . If it is written as a sum of three rotation gates, then it becomes
2
3N /4 . This requires either (2n − 1) or (2n) number of control qubits and 1 target qubit. The decomposition of a
multi controlled network into CNOTs and singlerotation gates can be done by following Ref.[18]. In that case, the
circuit for UH at this point would require N 2 /2 or N 2 number of CNOTs.
The generation of the circuit in Fig.2 necessitates two more qubits. This makes the number of qubits (2n + 1) or
(2n + 2) in total depending on the number of gates used for each A[... ] . The circuit has two networks UH controlled
by

2
2
(2n) or (2n + 1) qubits. Following Ref.[18] again, the decomposition of each network requires N or 2N CNOTs.
Since the
 complexity of B and Π are negligible in comparison to controlled UH , the total complexity is bounded by
O N2 .

V.

DISCUSSION AND FUTURE WORK
A.

Special Matrices

The described divide and conquer method groups the neighboring matrix elements into gates. Any sparsity in the
considered matrix may potentially reduce the number of A[... ] s. However, when the sparsity of the matrix is structured
as in tridiagonal, anti-tridiagonal, and band matrices; the number of terms and so the numbers of qubits and CNOTs
used in the circuit are directly affected.
For instance, the 16 × 16 Hamiltonian for the hydrogen molecule given in Ref.[17] (It can be easily written as a
sum of unitaries through Jordan-Wigner transformation) only have 4 non-diagonal elements, all of which are on the
anti-diagonal part of the Hamiltonian. If we consider the diagonal part and the anti-digonal part as a sum of two
unitaries, then the Hamiltonian can be written as sum of 4 number of Vj Pj terms. Since each Vj involves multicontrolled 8 quantum gates, in total there are 32 quantum gates. Then, UH requires 5 control- and 1 target-qubits.
Since an additional control qubit is necessary for U (t), there are two multi-controlled network, viz. two controlled
UH s, with 6 control qubits. The decomposition of these networks will constitute 128 CNOT gates in total. Here, note
that using U (t) in the phase estimation introduces an additional control qubit. Then the required number of CNOTs
for each iteration of the phase estimation algorithm is doubled to ≈ 256. Also note that in every iteration, only the
gates implementing B need to be updated and the rest of the circuit remains the same.

B.

Adaptive Processes

Finding the matrix elements of a Hamiltonian representing the dynamics of a quantum system is a nontrivial task
requiring tedious analytical and numerical computations. The circuit can be used to experimentally identify the
Hamiltonian dynamic of an unknown large system or estimate parameters of a quantum channels, where a known
state is sent through an unknown state and the measurement is used to estimate the parameters associated with the
channel [19]. A similar approach is used also in Ref.[20] to compress molecular Hamiltonians.
The matrix divided as in Eq.(14) can be also used to represent a layer of a neural network in matrix form. In
the learning or adaptive processes based on gradient-descent, when the eigenvalues of an autocorrelation matrix are
disparate: i.e. the condition number of the matrix is large, the leaning rate or the performance of an adaptive algorithm
are hindered in applications [21]. Therefore, in these processes, using the phase estimation[2] as an ingredient for
different algorithms may provide better performances. The phase estimation algorithm requires two registers to store
the eigenvalue and the eigenvector respectively. The size of the first register is determined by the desired accuracy:
e.g. for a 32-bit precision, it has 32 qubits. When the system size is large, the iterative phase estimation using only
a qubit in the first register is more preferred in the experiments and classical simulations. However, the iterative
version starts the estimation of the bits from the least significant bit (LSB) toward the most significant bit (MSB).
This impedes the employment of the algorithm as a subroutine in various multivariate statistical algorithms in which
the eigenvalues above or below some threshold are filtered out.

1.

Modified Iterative Phase Estimation

Fig.3 describes a slight modified version of the iterative phase estimation algorithm, where the bit values are
estimated starting from MSB: The algorithm works as follows:
6

B

Adaptive Processes

A

HAMILTONIAN IN THE RECURSION

FIG. 3: The iterative phase estimation for adaptive processes: H represents the Hadamard gate and k ≥ 1.

• Assume the circuit U and its eigenvector |ϕi are given. For simplicity also assume t = 1.
• In the first iteration k is set to 1: i.e., we have U (2π). After the controlled-U , the following state is obtained
(Normalization constants are omitted for simplicity.):
|ψ1 i = |0i |ϕi + eiπ(φ1 .φ2 ... )2 |1i |ϕi .

(25)

Here, (φ1 .φ2 . . . )2 represents the binary form of the phase multiplied by 2: 2φ.
• To make the real part
of the value eiπ(φ1 .φ2 ... )2 negative when φ1 = 1 and positive when φ1 = 0, we apply a

rotation Rz −π/2 :

Rz

π
−
2


=

1
0
0 e−iπ/2

!
.

(26)

Note that in general when rotation gate about the z-axis is defined, the angle is divided by 2, which is neglected
here. After this gate, we have:
|ψ2 i = |0i |ϕi + eiπ(φ1 .φ2 ... )2 −iπ/2 |1i |ϕi .

(27)

• The value of τ for the gate Rz (τ ) is computed from the previous iterations and it is zero for the first iteration.
• After applying the second Hadamard gate, the final state becomes the following:

|ψ3 i = 1 + cos (α) + isin (α) |0i |ϕi

+ 1 − cos (α) − isin (α) |1i) |ϕi ,

(28)

where α = π (φ1 .φ2 . . . )2 − π/2. The probability difference between |0i and |1i is determined by the value of
cos(α):
h
i
– If φ1 = 0, then α ∈ − π2 , π2 and cos(α) ≥ 0. Hence, the probability of |0i is higher than |1i.
h
i
– If φ1 = 1, then α ∈ π2 , 3π
and cos(α) ≤ 0. And so, the probability of |1i is higher than |0i.
2
• In the second iteration; k = 2 and if φ1 is 1, then τ is set to 1 × π to put the phase in the form (φ2 .φ3 . . . )2 .
The probability difference between |0i and |1i in the output may be as high as 1 or in rare cases is equal to 0. For
random 5000 matrices, the distribution of the probability differences is drawn Fig.4: The probability differences are
obtained by iterating the phase estimation algorithm 20 times for each matrix. As shown in the figure, the probability
to see the difference less than 0.1 is around 0.06. Therefore, this iterative version can be used in adaptive processes
to filter out some of the eigenvalues or prepare the ground state of the Hamiltonians.
MATLAB source codes for the circuits in the figures and for obtaining A[... ] , Vj , and Pj matrices are provided in
https://github.com/adaskin/circuitforTaylorseries.

Appendix A: Hamiltonian in the Recursion
1.

Second step (k = 2)

If we plug Eq.(12) in places of A[... ] s:
7

1

Second step (k = 2)

A

HAMILTONIAN IN THE RECURSION

FIG. 4: The histogram of the probability differences in the outputs of the iterative phase estimation for 5000
random matrices. The algorithm is iterated 20 times for each matrix. Here, the probability to see the probability
difference less than 0.1 is 0.0644 and greater than 0.9 is 0.2862.






H = |0i h0| |0i h0| A00 + |1i h1| A03 + X ⊗ IN/8 |0i h0| A01 + |1i h1| A02





+ |1i h1| |0i h0| A30 + |1i h1| A33 + X ⊗ IN/8 |0i h0| A31 + |1i h1| A32







+ X ⊗ IN/4 |0i h0| |0i h0| A10 + |1i h1| A13 + X ⊗ IN/8 |0i h0| A11 + |1i h1| A12







+ X ⊗ IN/4 |1i h1| |0i h0| A20 + |1i h1| A23 + X ⊗ IN/8 |0i h0| A21 + |1i h1| A22 .

(A1)

This gives the following:




H = |00i h00| A00 + |01i h01| A03 + I ⊗ X ⊗ IN/8 |00i h00| A01 + |01i h01| A02



+ |10i h10| A30 + |11i h11| A33 + I ⊗ X ⊗ IN/8 |10i h10| A31 + |11i h11| A32



 

+ X ⊗ I ⊗ IN/8 |00i h00| A10 + |01i h01| A13 + X ⊗ X ⊗ IN/8 |00i h00| A11 + |01i h01| A12



 

+ X ⊗ I ⊗ IN/8 |10i h10| A20 + |11i h11| A23 + X ⊗ X ⊗ IN/8 |10i h10| A21 + |11i h11| A22 ,

which can be rewritten as in Eq.(14).
8

(A2)

1

Second step (k = 2)

A
2.

HAMILTONIAN IN THE RECURSION

Third step (k = 3)

Then, in the third recursion, we get the following:
H =|0|A000 + |1|A003 + |2|A030 + |3|A033 + |4|A300 + |5|A303 + |6|A330 + |7|A333


+ I ⊗ I ⊗ X ⊗ IN/8
|0|A001 + |1|A002 + |2|A031 + |3|A032 + |4|A301 + |5|A302 + |6|A331 + |7|A332


+ I ⊗ X ⊗ I ⊗ IN/8



|0|A010 + |1|A013 + |2|A020 + |3|A023 + |4|A310 + |5|A313 + |6|A320 + |7|A323


+ I ⊗ X ⊗ X ⊗ IN/8



|0|A011 + |1|A012 + |2|A021 + |3|A022 + |4|A311 + |5|A312 + |6|A321 + |7|A322


+ X ⊗ I ⊗ I ⊗ IN/8



|0|A100 + |1|A103 + |2|A030 + |3|A033 + |4|A200 + |5|A203 + |6|A230 + |7|A233


+ X ⊗ I ⊗ X ⊗ IN/8



|0|A101 + |1|A102 + |2|A031 + |3|A032 + |4|A201 + |5|A202 + |6|A231 + |7|A232


+ X ⊗ X ⊗ I ⊗ IN/8



|0|A110 + |1|A113 + |2|A123 + |3|A123 + |4|A210 + |5|A213 + |6|A220 + |7|A223


+ X ⊗ X ⊗ X ⊗ IN/8



(A3)


|0|A111 + |1|A112 + |2|A121 + |3|A122 + |4|A211 + |5|A212 + |6|A221 + |7|A222 ,
where |i| = |ii hi|. This Hamiltonian in matrix form corresponds to the following matrix:


 A000
 A002

 A020


A022

H = 

 A200
 A202

 A220

A222


A001
A003 
A021
A023

A201
A203 
A221
A223



A010
A012
A030
A032

A210
A212
A230
A232


A011

A013 

A031 
A033

A211

A213 

A231 
A233


A
 100
A102

 A120
A122

A
 300
A302

 A320
A322


A101
A103 
A121
A123

A301
A303 
A321
A323



A110
A
 112
A130
A132

A310
A
 312
A330
A332



A111

A113 

A131 


A133

 .

A311

A323 

A331 

A333

(A4)

[1] Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari, and Rolando D Somma, “Simulating hamiltonian
dynamics with a truncated taylor series,” Physical review letters 114, 090502 (2015).
[2] Alexei Kitaev, “Quantum measurements and the Abelian Stabilizer Problem,” Electronic Colloquium on Computational
Complexity (ECCC) 3 (1996).
[3] Hale F Trotter, “On the product of semi-groups of operators,” Proceedings of the American Mathematical Society 10,
545–551 (1959).
[4] Masuo Suzuki, “Generalized trotter’s formula and systematic approximants of exponential operators and inner derivations
with applications to many-body problems,” Communications in Mathematical Physics 51, 183–190 (1976).
[5] David Poulin, Matthew B. Hastings, Dave Wecker, Nathan Wiebe, Andrew C. Doberty, and Matthias Troyer, “The trotter
step size required for accurate quantum simulation of quantum chemistry,” Quantum Information and Computation 15,
361–384 (2015).
[6] Ammar Daskin and Sabre Kais, “An ancilla-based quantum simulation framework for non-unitary matrices,” Quantum
Information Processing 16, 33 (2017).

9

2

Third step (k = 3)

A

HAMILTONIAN IN THE RECURSION

[7] Guang Hao Low and Isaac L Chuang, “Optimal hamiltonian simulation by quantum signal processing,” Physical review
letters 118, 010501 (2017).
[8] David Poulin, Alexei Kitaev, Damian S Steiger, Matthew B Hastings, and Matthias Troyer, “Fast quantum algorithm for
spectral properties,” arXiv preprint arXiv:1711.11025 (2017).
[9] Ammar Daskin and Sabre Kais, “Direct application of the phase estimation algorithm to find the eigenvalues of the
hamiltonians,” arXiv preprint arXiv:1703.03597 (2017).
[10] Ryan Babbush, Dominic W Berry, Yuval R Sanders, Ian D Kivlichan, Artur Scherer, Annie Y Wei, Peter J Love, and
Aln Aspuru-Guzik, “Exponentially more precise quantum simulation of fermions in the configuration interaction representation,” Quantum Science and Technology 3, 015006 (2018).
[11] Anmer Daskin, Ananth Grama, Giorgos Kollias, and Sabre Kais, “Universal programmable quantum circuit schemes to
emulate an operator,” The Journal of chemical physics 137, 234112 (2012).
[12] Ryan Babbush, Dominic Berry, Mária Kieferová, Guang Hao Low, Yuval Sanders, Artur Scherer, and Nathan Wiebe,
“Improved techniques for preparing eigenstates of fermionic hamiltonians,” arXiv preprint arXiv:1711.10460 (2017).
[13] Guang Hao Low and Isaac L Chuang, “Hamiltonian simulation by uniform spectral amplification,” arXiv preprint
arXiv:1707.05391 (2017).
[14] Guang Hao Low and Isaac L Chuang, “Hamiltonian simulation by qubitization,” arXiv preprint arXiv:1610.06546 (2016).
[15] Pei Wu, “Additive combinations of special operators,” Banach Center Publications 30, 337–361 (1994).
[16] Benjamin P Lanyon, James D Whitfield, Geoff G Gillett, Michael E Goggin, Marcelo P Almeida, Ivan Kassal, Jacob D
Biamonte, Masoud Mohseni, Ben J Powell, Marco Barbieri, et al., “Towards quantum chemistry on a quantum computer,”
Nature Chemistry 2, 106–111 (2010).
[17] Jacob T. Seeley, Martin J. Richard, and Peter J. Love, “The bravyi-kitaev transformation for quantum computation of
electronic structure,” The Journal of Chemical Physics 137, 224109 (2012).
[18] Mikko Möttönen, Juha J. Vartiainen, Ville Bergholm, and Martti M. Salomaa, “Quantum circuits for general multiqubit
gates,” Physical Review Letters 93, 130502 (2004).
[19] BM Escher, RL de Matos Filho, and L Davidovich, “General framework for estimating the ultimate precision limit in
noisy quantum-enhanced metrology,” Nature Physics 7, 406–411 (2011).
[20] Jonathan Romero, Jonathan P Olson, and Alan Aspuru-Guzik, “Quantum autoencoders for efficient compression of
quantum data,” Quantum Science and Technology 2, 045001 (2017).
[21] Bernard Widrow, John M McCool, Michael G Larimore, and C Richard Johnson, “Stationary and nonstationary learning
characteristics of the lms adaptive filter,” Proceedings of the IEEE 64, 1151–1162 (1976).

10

