Perturbation theory with quantum signal processing

2025-05-02 0 0 737.45KB 17 页 10玖币

侵权投诉

Kosuke Mitarai1,2, Kiichiro Toyoizumi3, and Wataru Mizukami2

1Graduate School of Engineering Science, Osaka University, 1-3 Machikaneyama, Toyonaka, Osaka 560-8531, Japan.

2Center for Quantum Information and Quantum Biology, Osaka University, Japan.

3Graduate School of Science and Technology, Keio University, 3-14-1 Hiyoshi, Kohoku-ku, Yokohama 223-8522, Japan.

May 11, 2023

Perturbation theory is an important technique

for reducing computational cost and providing

physical insights in simulating quantum systems

with classical computers. Here, we provide a

quantum algorithm to obtain perturbative ener-

gies on quantum computers. The beneﬁt of us-

ing quantum computers is that we can start the

perturbation from a Hamiltonian that is classi-

cally hard to solve. The proposed algorithm uses

quantum signal processing (QSP) to achieve this

goal. Along with the perturbation theory, we

construct a technique for ground state prepara-

tion with detailed computational cost analysis,

which can be of independent interest. We also

estimate a rough computational cost of the algo-

rithm for simple chemical systems such as water

clusters and polyacene molecules. To the best of

our knowledge, this is the ﬁrst of such estimates

for practical applications of QSP. Unfortunately,

we ﬁnd that the proposed algorithm, at least in

its current form, does not exhibit practical num-

bers despite of the eﬃciency of QSP compared

to conventional quantum algorithms. However,

perturbation theory itself is an attractive di-

rection to explore because of its physical inter-

pretability; it provides us insights about what

interaction gives an important contribution to

the properties of systems. This is in sharp con-

trast to the conventional approaches based on

the quantum phase estimation algorithm, where

we can only obtain values of energy. From this

aspect, this work is a ﬁrst step towards “ex-

plainable” quantum simulation on fault-tolerant

quantum computers.

1 Introduction

Perturbation theory is one of the most important tech-

niques to understand quantum systems. It solves prob-

lems by separating them into easy parts and diﬃcult

Kosuke Mitarai: mitarai.kosuke.es@osaka-u.ac.jp

ones, and gradually taking the eﬀect of diﬃcult parts

into account. For weakly correlated systems, it usu-

ally gives suﬃciently accurate physics of the systems.

A beneﬁt of using perturbative methods is its computa-

tional eﬃciency compared to the cost of exactly solving

quantum systems. The computational cost to obtain

an exact solution of an n-body quantum system is gen-

erally exponential to non classical computers, while

that of perturbative methods is only polynomial. An-

other important aspect of perturbation is its physical

interpretability. It provides us insights into what eﬀect

a speciﬁc interaction of the system has on its overall

physical properties.

In this work, we provide a method to implement per-

turbation theory on quantum computers and discuss if

the beneﬁts described above can also be obtained. Our

method allows one to use strongly-interacting Hamilto-

nians that are only solvable with quantum computers

as a starting point of the perturbation. More speciﬁ-

cally, our algorithm ﬁrst constructs a ground state of an

unperturbed Hamiltonian via quantum signal process-

ing (QSP) [1–3] and ﬁxed-point amplitude ampliﬁcation

[4]. Then, we generate a perturbative state by applying

the inverse of an unperturbed Hamiltonian with quan-

tum signal processing (QSP), and obtain an expectation

value of a perturbation operator via robust amplitude

estimation (RAE) [5–7].

For an unperturbed Hamiltonian Hand perturba-

tion Vthat can be written as H=P`h`σ`and V=

P`v`σ`where σ`are Pauli operators, the complexity

of the proposed algorithm is ˜

O(khk1kvk2/3/(∆δ)) and

O(khk1kvk2

2/3/(∆2δ)) respectively for the ﬁrst-order

and second-order perturbation, where ∆is a spectral

gap of H,δis error in the estimated perturbation en-

ergy and kakp= (P`ap

`)1/p.

We also perform a concrete resource analysis of the

algorithm for simple chemical systems such as water

clusters and polyacenes to discuss its practicality. This

is, to the best of our knowledge, the ﬁrst such analy-

sis of a practical application of the QSP and the QSP-

based matrix inversion technique. Despite of eﬃciency

of QSP compared to conventional techniques, it is found

Accepted in Quantum 2023-04-04, click title to verify 1

arXiv:2210.00718v3 [quant-ph] 10 May 2023

that our algorithm gives impractical numbers as com-

putational cost; for example, we estimate over 1031

calls of block-encodings would be required to perform

perturbation on a pentacene molecule. This is much

larger than the cost required for naively performing the

phase estimation of the total Hamiltonian, which only

requires 1010 calls of block-encodings. While we could

not achieve a reduction of computational cost like the

classical perturbation theory, the other beneﬁt of per-

turbation, that is, the interpretability of the result, is

still an important point. Conventional techniques of

quantum simulations based on phase estimation can

give us energy and its eigenstates, but cannot provide

us insights into why the energy is the obtained value.

We, therefore, believe this work is a ﬁrst step toward

an “explainable” quantum simulation on fault-tolerant

quantum computers.

2 Preliminaries

2.1 Perturbation theory

We have an n-qubit Hamiltonian Htotal =H+V. We

consider the Hamiltonian Hand the perturbation V

that can be decomposed into Pauli operators σ`as,

`=1

h`σ`(1)

`=1

v`σ`(2)

Note that Hand Vcan, without loss of generality,

be deﬁned as not having I⊗nterm. Let the ground

state of Htotal with eigenvalue E0be |E0i. Also, let

an eigenstate Hwith an eigenvalue ibe |ii. We as-

sume that the eigenvalues are ordered in ascending or-

der 0< 1≤ ··· ≤ 2n−1.

It is well known [8] that |E0ican be approximated as

|E0i≈|(1)

0i(3)

:= |0i − Π(H−0)−1ΠV|0i,(4)

where Π = I−|0ih0|, to the ﬁrst order in kVkif iis

not degenerate. The corresponding eigenvalue E0can

be approximated as,

E0≈0+(1)

0+(2)

0,(5)

where

(1)

0=h0|V|0i(6)

and

(2)

0=−h0|VΠ(H−0)−1ΠV|0i.(7)

2.2 Block-encoding of a Hamiltonian

First, we introduce the block-encoding [3,9]. We say a

unitary UAblock-encodes a matrix Awhen it has the

following form:

UA=A/α ·

· · .(8)

More formally, we say (n+l)-qubit unitary UAis a

(α, l, ε)-block encoding of n-qubit operator Aif



A−αh0l| ⊗ IU|0li ⊗ I

≤ε. (9)

Babbush et al. [10] showed that we can perform phase

estimation of a unitary eiarccos A/α to estimate an eigen-

value of Ato precision δby using UAfor √2πα

2δtimes.

The phase estimation algorithm [11] takes in a state

|ψiand outputs eigenvalue eiφ of a unitary Uwith a

probability p(φ) = |hφ|ψi|2where |φiis the eigenstate

of Ucorresponding to the eigenvalue eiφ. If we wish

to obtain a speciﬁc eigenvalue such as the ground state

energy, |ψimust therefore have non-negligible overlap

with the corresponding eigenstate.

An explicit block-encoding of an n-qubit operator A

which can be represented as a sum of Pauli operator as

A=PL

`=1 a`σ`can be constructed via PREPAREaand

SELECT operations introduced in Ref. [10]. PREPARE

operation acts on l=dlog2Lequbits as

PREPAREa|0li=

L−1

`=0 ra`

kak1|`i ≡ |Lµi.(10)

where kak1=P`|a`|.SELECT acts on n+lqubits and

deﬁned as

SELECT =

L−1

`=0 |`ih`| ⊗ σ`.(11)

Then,

UA=PREPARE†

a·SELECT ·PREPAREa(12)

satisﬁes (h0l|⊗In)UA(|0li⊗In) = A/kak1, i.e., UAis a

(kak1, l, 0)-block-encoding of A. It has been shown that

PREPAREaand SELECT operations can be implemented

with O(L+ log(1/ε)) T gates. Note that the T gate is

the most time-consuming gate in the surface-code-based

fault-tolerant quantum computing [10].

2.3 Eigenvalue transformation via quantum sig-

nal processing

Given a block-encoding UAof A, we can construct a

block encoding of P(A)for certain polynomials P(x)

Accepted in Quantum 2023-04-04, click title to verify 2

[1–3]. In this work, we are only interested in real poly-

nomials P(x). The seminal work [3, Corollary 10] shows

that, for a degree-dreal polynomial P(x)such that

|P(x)| ≤ 1for |x| ≤ 1,(13)

P(x) = P(−x)if dis even,

P(x) = −P(−x)if dis odd (14)

we can obtain a unitary P0and P1such that

P0|0li|ψi=|0li[˜

P(A)|ψi] + |gi,(15)

P1|0li|ψi=|0li[˜

P∗(A)|ψi] + |gi,(16)

where ˜

P(x)is a degree-dpolynomial such that

Re[ ˜

P(x)] = P(x),∗denotes complex conjugate,

and |giis a “garbage” state which is orthogonal to

|0li[˜

P(A)|ψi]. We can construct P0and P1with d

calls of UA. Moreover, a unitary deﬁned as

P=|+ih+|⊗P0+|−ih−| ⊗ P1,(17)

which uses another ancilla qubit, satisﬁes

P |0l+1i|ψi=|0l+1i[P(A)|ψi] + |gi(18)

as shown in [3, Corollary 18]. Note that Pcan be con-

structed by only using d-calls of UArather than 2d-calls,

since P1is obtained by inverting phase sequences of P0

[3, Corollary 18]. After the application of P, we can

post-select on the ancilla being |0l+1ito obtain a state

proportional to P(A)|ψi. The probability of success is

kP(A)|ψik2. This procedure is called quantum signal

processing (QSP) [1–3]. In this work, we say a polyno-

mial is QSP-implementable if it satisﬁes the above two

conditions (13)and (14).

2.4 Amplitude estimation

Amplitude estimation refers to various techniques to ob-

tain values of amplitudes of a quantum state |ψiwithin

error of δusing O(1/δ)calls of a state preparation uni-

tary Uψsuch that |ψi=Uψ|0i. The original algorithm

can be found in [12]. Recent developments have made

the procedure signiﬁcantly more eﬃcient. For exam-

ple, a state-of-the-art method called the robust ampli-

tude estimation (RAE) [5–7] can empirically estimate

hψ|σ|ψifor a Pauli operator σwithin a mean squared

error of δ2by using

5√2

e−1

δ(19)

calls of Uψ. Other recent works such as iterative quan-

tum amplitude estimation [13,14] have shown similar

performance. In this work, we employ RAE to estimate

the expectation values.

3 Perturbation theory on quantum com-

puters

3.1 High-level overview

Our approach for performing perturbation on a quan-

tum computer is as follows:

1. Perform phase estimation of Hto estimate 0

within a precision of δ0.

2. Eﬃciently generate |0ivia QSP-based eigenstate

ﬁltering (Sec. 3.2).

3. Estimate the ﬁrst-order perturbation energy by

measuring h0|V|0i(Sec. 3.3).

4. Estimate the second-order perturbation energy by

performing the Hadamard test of a unitary which

approximates Π(H−0)−1Πconstructed via QSP

(Sec. 3.4).

Step 1 of the algorithm can be replaced with more so-

phisticated techniques provided in Refs. [15,16] from

the naive phase estimation. Algorithms for step 2 are

also proposed in e.g. [15,17,18], but previous works dis-

cuss the cost in terms of O-notations. In the following

subsections, we describe the details of steps 2, 3, and 4,

without resorting to O-notations. Some assumptions we

make are in order. First, we assume that one can pre-

pare a state |ψithat has non-zero overlap pwith |0iin

steps 1 and 2. We do not discuss how to choose and pre-

pare such a state in detail because they strongly depend

on the target system. For our numerical resource esti-

mation in Sec. 4, we employ Hartree-Fock states. The

second assumption is the knowledge of lower bounds to

the overlap pand the spectral gap ∆ = 1−0of the un-

perturbed Hamiltonian H. This assumption is required

for constructing quantum circuits for steps 2 and 4. In

the following, we formulate the cost by using pand ∆

but they can always be replaced by their lower bounds.

We note that Ref. [19] has considered a similar task

that involves the inversion of Hamiltonians using QSP.

Their main target is, however, to calculate Green’s func-

tion, which is widely used to obtain response properties

with respect to external ﬁelds, and not to construct gen-

eral perturbation theory, which can evaluate the energy

of a many-body system, like this work. From the tech-

nical viewpoint, for the calculation of Green’s function,

only the operator in the form of (H−z)−1where zis

a complex number is required and one does not need

to construct Π(H−0)−1Πas we do here. Ref. [20]

also considers the perturbative simulation of quantum

systems. Their goal is to implement real-time dynamics

on a quantum computer and does not focus on obtain-

ing the energies of Hamiltonians. It is achieved by ﬁrst

Accepted in Quantum 2023-04-04, click title to verify 3

discretizing the time evolution to small time slices and

sampling the perturbative part of each of the short-time

dynamics with respect to a quasi-probability distribu-

tion. Their method hence requires exponential cost with

respect to the evolution time, and would not be suitable

for extracting energy eigenvalues with high precision.

3.2 Preparation of a reference state

In this work, we utilize the QSP-approximation of rect-

angular functions introduced by Low and Chuang [21]

and reviewed in Ref. [2] to prepare the reference state

|0ifrom which we start the perturbation. |0ican be

generated via phase estimation. However, it is more ef-

ﬁcient to use QSP to ﬁlter |0iwhen we know the value

of the corresponding eigenvalue 0. The construction of

rectangular functions closely follows that of [2,21] but

we give more detailed cost, that is, the degree of polyno-

mial needed for their approximation, than the previous

works. In Appendix A, we show that there exists a

QSP-implementable polynomial Pﬁlter

ε,κ,xth (x)such that,

Pﬁlter

ε,κ,xth (x)>1−ε(|x|< xth),

|Pﬁlter

ε,κ,xth (x)|< ε (|x|> xth +κ),(20)

where xth >0,0< κ < 2(1 −xth)are parameters, with

degree roughly

nﬁlter(ε, κ, xth)

≈64(1 + x0

th)

√πε

κs2 loge8

πε2exp −1

2W2048

πε2e2,

(21)

where x0

th =xth +κ/2and W(x)is the Lambert W

function. We plot the values of nﬁlter(ε, κ, xth)as Fig. 1

with various parameter settings. Using an inequality

W(x)>log(x)−log(log(x)), we can roughly upper-

bound nﬁlter(ε, κ, xth)by,

nﬁlter(ε, κ, xth)

≤e(1 + x0

th)

√2κsloge8

πε2loge2048

πε2e2,(22)

which has O(log(1/ε)/κ)scaling.

Let us assume that we know an estimate ˆ0of 0such

that |ˆ0−0|< δ0. Deﬁne H0=H−ˆ0I. Let

H0=

LH+1

`=1

`σ`.(23)

Note that, since we assume that Hdoes not have

I⊗nterm, H0has LH+ 1 terms. Also, note that

kh0k1=khk1+|ˆ0|. Let l0=dlog(LH+ 1)e, the num-

ber of ancilla qubits needed to block-encode H0. We

Figure 1: Values of nﬁlter calculated by Eq. (21)with xth =

10−6, which is a typical value for the molecules studied in

Sec. 4, and with diﬀerent error parameters εas a function

of κ. Points corresponds to the values for speciﬁc molecules

presented in Tables 2and 3.

can perform QSP of H0via UH0. QSP can construct

Pﬁlter

ε,κ (H0/kh0k1)with nﬁlter(ε, κ, xth)calls of UH0(see

Sec. 2.3). Then, since we know the ground state energy

of H0/kh0k1is within [−δ0/kh0k1, δ0/kh0k1]and the sec-

ond largest energy is larger than (∆−δ0)/kh0k1, we can

set

xth =δ0/kh0k1,(24)

κ= (∆ −δ0)/kh0k1,(25)

The error parameter εcontrols the ﬁdelity of |0i. Let

us assume an initial state |ψifed to the QSP satisﬁes,

|ψi=√p|0i+p1−p|⊥

0i,(26)

where |⊥

0iis a state orthogonal to |0i. To obtain |0i,

we ﬁrst apply Pﬁlter

ε,κ,xth (H0/kh0k1)via QSP and get a

state in the form of,

|0l0+1iPﬁlter

ε,κ,xth H0

kh0k1|ψi+|gi.(27)

The post-selection on the ancilla being |0iresults in a

state

|˜0i=Pﬁlter

ε,κ,xth (H0/kh0k1)|ψi/kPﬁlter

ε,κ,xth (H0/kh0k1)|ψik,

(28)

which is used as the reference state for the perturbation.

We obtain the perturbation energies as expectation val-

ues of observables O=Vand VΠ(H−0)ΠVwith

respect to |˜0i. We, therefore, wish to make

δprep := |h0|O|0i−h˜0|O|˜0i|  δ(29)

to obtain the perturbation energy with an accuracy of

δ. In Appendix B, it is shown that,

δprep = 2εr1−p

pRe h⊥

0|O|0i+O(ε2) (30)

Accepted in Quantum 2023-04-04, click title to verify 4

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

PerturbationtheorywithquantumsignalprocessingKosukeMitarai1,2,KiichiroToyoizumi3,andWataruMizukami21GraduateSchoolofEngineeringScience,OsakaUniversity,1-3Machikaneyama,Toyonaka,Osaka560-8531,Japan.2CenterforQuantumInformationandQuantumBiology,OsakaUniversity,Japan.3GraduateSchoolofScienceandTechnolo...

展开>> 收起<<

Perturbation theory with quantum signal processing.pdf

共17页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Perturbation theory with quantum signal processing

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: