Quantifying T-gate-count improvements for ground-state-energy estimation with near-optimal state preparation S. Pathak1A.E. Russo1S.K. Seritan2and A.D. Baczewski1

2025-05-02 0 0 1.39MB 24 页 10玖币

侵权投诉

Quantifying T-gate-count improvements for ground-state-energy estimation with

near-optimal state preparation

S. Pathak,1A.E. Russo,1S.K. Seritan,2and A.D. Baczewski1

1Quantum Algorithms and Applications Collaboratory,

Sandia National Laboratories, Albuquerque NM, USA

2Quantum Algorithms and Applications Collaboratory,

Sandia National Laboratories, Livermore CA, USA

We study the question of when investing additional quantum resources in preparing a ground state

will improve the aggregate runtime associated with estimating its energy. We analyze Lin and Tong’s

near-optimal state preparation algorithm and show that it can reduce a proxy for the runtime, the

T-gate count, of ground state energy estimation near quadratically. Resource estimates are provided

that specify the conditions under which the added cost of state preparation is worthwhile.

Introduction.— A key task in all quantum simulation

algorithms is the preparation of a state that encodes the

observables of a physical system of interest [1–3]. This

is often the ground state |Ψ0iof a Hamiltonian Hon

an n-qubit Hilbert space [4–8]. Independent of whether

this represents interacting electrons [9–14], spins [15–

17], or quantum ﬁelds [18–20], we generally produce an

approximation to the desired state |Φ0iwith overlap

γ=|hΦ0|Ψ0i|. Then the probability of successfully pro-

cessing |Φ0ito estimate some observable of interest (e.g.,

the ground state energy E0) is generally upper bounded

by γ2[21], which would ideally be 1.

While it is likely not possible to eﬃciently prepare

ground states of generic local Hamiltonians on quantum

computers [22,23] physical arguments suggest that the

speciﬁc instances for which nature can eﬃciently ﬁnd the

ground state will be eﬃciently preparable on a quantum

computer [24]. Though the question of which instances

these are remains an active area of research [25], it is gen-

erally of interest to develop algorithms that increase γi

from some easy-to-prepare initial approximation, |Φ0,ii,

to γfwith some associated ﬁnal approximation |Φ0,f i.

It might be that |Φ0,iicomes from the outcome of a

classical calculation (e.g., an approximate solution to

a mean-ﬁeld theory) or a hybrid quantum-classical ap-

proach like the variational quantum eigensolver [26,27].

Regardless of the source of |Φ0,ii, it is often assumed

that the cost of preparing it is negligible relative to the

cost of boosting γi→γf, making use of some unitary

USP (H)|Φ0,ii=|Φ0,f i[28].

The question that we answer in this Letter is “when

does the added cost of implementing USP (H) outweigh

the cost of repeated trials with a lower probability

of success?” We are speciﬁcally concerned with the

potential beneﬁt to estimating E0, for which conven-

tional approaches that apply quantum phase estimation

(QPE) [29] to |Φ0,iiwill project onto |Ψ0iafter a single

round with probability γ2

i[21] (see Fig. 1(a)). One can

use more elaborate strategies in which repeated rounds of

QPE can iteratively improve our knowledge of E0[2,30–

35], though we assume a simple strategy of repeating the

circuit O(γ−2

i) times for ease of analysis [36].

Broadly speaking there are two classes of state prepa-

ration algorithms, those that make use of the adiabatic

theorem [37] and those that apply a ﬁlter in the eigen-

basis of H[4]. In this Letter, we consider a USP (H) in

the latter category, derived from a near-optimal approach

of Lin and Tong [7]. While adiabatic state prepara-

tion is conceptually straightforward, it generally requires

time-dependent Hamiltonian simulation, the analysis of

a family of Hamiltonians along the entire adiabatic path-

way, and potentially many diﬀerent initial Hamiltonians,

rather than a single instance. It also has worse scaling

with the minimum spectral gap [38]. However, there are

some important exceptions [39] and it may be the case

that adiabatic algorithms are found to be the optimal

solution in some cases, so we make no claim to the op-

timality of our results. An added beneﬁt of analyzing

ﬁlter-based state preparation is that it relies on a block

encoding [40] of Hthat could be identical to one used in

QPE, making it straightforward to compare costs.

Whether exponential, polynomial, or nonexistent, the

advantages realized by quantum computers in physi-

cal simulation are likely to be problem-speciﬁc and de-

pend critically on the cost of implementing USP (H) [41].

We provide estimates for the cost of state preparation

based on the T-gate count of implementations of Lin and

Tong’s USP (H) [7]. We choose the total number of T

gates as a simple-to-compute proxy for an actual run-

time estimate because their implementation will domi-

nate the runtime in T-factory-limited surface code ar-

chitectures [42,43] and a more precise analysis would

involve detailed scheduling of the algorithm’s implemen-

tation. Actual runtimes could also be reduced relative to

this proxy in contexts in which the availability of magic

states is not a limiting factor, in which case the Tdepth

would be the more appropriate quantiﬁer.

We propose a ratio ιthat compares the T-gate count

for USP (H) and subsequent QPE to the count for “triv-

ial” state prep and QPE repeated until success. This

quantiﬁes the improvement in runtime associated with

“better” state preparation and allows us to answer the

arXiv:2210.10872v3 [quant-ph] 17 Apr 2023

<latexit sha1_base64="FRtXdbdcvWMed+L/CceW71gkdRw=">AAACCnicbVA9SwNBEN2LXzF+RS1tVoNgFe6ComXAxjKC+YAkhrnNJlmye3fszqnhSFob/4qNhSK2/gI7/42bj0ITHww83pthZp4fSWHQdb+d1NLyyupaej2zsbm1vZPd3auYMNaMl1koQ13zwXApAl5GgZLXIs1B+ZJX/f7l2K/ecW1EGNzgIOJNBd1AdAQDtFIrezhqIH/A5F5gj0Y69MEXUuBgOGp0QSm4LbSyOTfvTkAXiTcjOTJDqZX9arRDFiseIJNgTN1zI2wmoFEwyYeZRmx4BKwPXV63NADFTTOZvDKkx1Zp006obQVIJ+rviQSUMQPl204F2DPz3lj8z6vH2LloJiKIYuQBmy7qxJJiSMe50LbQnKEcWAJMC3srZT3QwNCml7EhePMvL5JKIe+d5d3r01zxaBZHmhyQI3JCPHJOiuSKlEiZMPJInskreXOenBfn3fmYtqac2cw++QPn8weZBZta</latexit>

with probability 2

<latexit sha1_base64="MAmt696dWbtP/hYlHsocyYumFSs=">AAAB9XicbVBNS8NAEJ34WetX1aOXpUXwVBJR9Fjw4rGC/YA2ls120i7dbMLuRimx/8OLB0W8+l+8+W/ctjlo64OBx3szzMwLEsG1cd1vZ2V1bX1js7BV3N7Z3dsvHRw2dZwqhg0Wi1i1A6pRcIkNw43AdqKQRoHAVjC6nvqtB1Sax/LOjBP0IzqQPOSMGivdP3XrmvfcrqJyILBXqrhVdwayTLycVCBHvVf66vZjlkYoDRNU647nJsbPqDKcCZwUu6nGhLIRHWDHUkkj1H42u3pCTqzSJ2GsbElDZurviYxGWo+jwHZG1Az1ojcV//M6qQmv/IzLJDUo2XxRmApiYjKNgPS5QmbE2BLKFLe3EjakijJjgyraELzFl5dJ86zqXVTd2/NKrZzHUYBjKMMpeHAJNbiBOjSAgYJneIU359F5cd6dj3nripPPHMEfOJ8/XV6SUg==</latexit>

| 0i

<latexit sha1_base64="5OIFtx87+Iq34DUlVu1d4n+2+fM=">AAACBnicbVBNS8NAEJ34WetX1KMIoUWol5KIoseClx4rmLbQhrDZbtulm03Y3Qgl5OTFv+LFgyJe/Q3e/Ddu2iDa+mDg8d4MM/OCmFGpbPvLWFldW9/YLG2Vt3d29/bNg8O2jBKBiYsjFolugCRhlBNXUcVINxYEhQEjnWByk/udeyIkjfidmsbEC9GI0yHFSGnJN0/6IVJjjFjqZn4q46z2IzSzM9+s2nV7BmuZOAWpQoGWb372BxFOQsIVZkjKnmPHykuRUBQzkpX7iSQxwhM0Ij1NOQqJ9NLZG5l1qpWBNYyELq6smfp7IkWhlNMw0J35jXLRy8X/vF6ihtdeSnmcKMLxfNEwYZaKrDwTa0AFwYpNNUFYUH2rhcdIIKx0cmUdgrP48jJpn9edy7p9e1FtVIo4SnAMFaiBA1fQgCa0wAUMD/AEL/BqPBrPxpvxPm9dMYqZI/gD4+Mbx4qZNQ==</latexit>

Usp(H)

<latexit sha1_base64="xj2yyuNHroUDzTLkTmqB+lzx/R4=">AAAB+HicbVBNS8NAEJ34WetHox69hBbBU0lE0WPBi8cK9gPaEDbbabt0swm7GyHG/hIvHhTx6k/x5r9x2+agrQ8GHu/NMDMvTDhT2nW/rbX1jc2t7dJOeXdv/6BiHx61VZxKii0a81h2Q6KQM4EtzTTHbiKRRCHHTji5mfmdB5SKxeJeZwn6ERkJNmSUaCMFduXJ7UsiRhyDXGVqGtg1t+7O4awSryA1KNAM7K/+IKZphEJTTpTqeW6i/ZxIzSjHabmfKkwInZAR9gwVJELl5/PDp86pUQbOMJamhHbm6u+JnERKZVFoOiOix2rZm4n/eb1UD6/9nIkk1SjoYtEw5Y6OnVkKzoBJpJpnhhAqmbnVoWMiCdUmq7IJwVt+eZW0z+veZd29u6g1qkUcJTiBKpyBB1fQgFtoQgsopPAMr/BmPVov1rv1sWhds4qZY/gD6/MHOiOTXA==</latexit>

|0isys

<latexit sha1_base64="TjOuzxUSv9tQuIjyB7G0FCxBPts=">AAAB+HicbVBNS8NAEJ3Ur1o/GvXoJbQInkoiih4LXjxWsB/QlrDZTtqlm03c3Qg19pd48aCIV3+KN/+N2zYHbX0w8Hhvhpl5QcKZ0q77bRXW1jc2t4rbpZ3dvf2yfXDYUnEqKTZpzGPZCYhCzgQ2NdMcO4lEEgUc28H4eua3H1AqFos7PUmwH5GhYCGjRBvJt8tPbk8SMeToZ/cJTn276tbcOZxV4uWkCjkavv3VG8Q0jVBoyolSXc9NdD8jUjPKcVrqpQoTQsdkiF1DBYlQ9bP54VPnxCgDJ4ylKaGdufp7IiORUpMoMJ0R0SO17M3E/7xuqsOrfsZEkmoUdLEoTLmjY2eWgjNgEqnmE0MIlczc6tARkYRqk1XJhOAtv7xKWmc176Lm3p5X65U8jiIcQwVOwYNLqMMNNKAJFFJ4hld4sx6tF+vd+li0Fqx85gj+wPr8ARQZk0M=</latexit>

|0iqpe

(a)

<latexit sha1_base64="ICswPzaU6KobC0O9ClgJ2AsvCx0=">AAAB8XicbVDLSgNBEJyNrxhfUY9ehgTBU9gVX8eACB4TMA9MljA76SRDZmeXmV4xLPkLLx4U8erfePNvnCR70GhBQ1HVTXdXEEth0HW/nNzK6tr6Rn6zsLW9s7tX3D9omijRHBo8kpFuB8yAFAoaKFBCO9bAwkBCKxhfz/zWA2gjInWHkxj8kA2VGAjO0Er3XYRHTOu1m2mvWHYr7hz0L/EyUiYZar3iZ7cf8SQEhVwyYzqeG6OfMo2CS5gWuomBmPExG0LHUsVCMH46v3hKj63Sp4NI21JI5+rPiZSFxkzCwHaGDEdm2ZuJ/3mdBAdXfipUnCAovlg0SCTFiM7ep32hgaOcWMK4FvZWykdMM442pIINwVt++S9pnla8i8p5/axcLWVx5MkRKZET4pFLUiW3pEYahBNFnsgLeXWM8+y8Oe+L1pyTzRySX3A+vgGXoZDH</latexit>

QPE

<latexit sha1_base64="5cMK/55s7gVKpM5n7SydC5xP7P4=">AAACCnicbVDJSgNBEO2JW4xb1KOXNkHwFGbE7RgQwWMEs0ASQk+nJmnSs9BdI4YhuXrxV7x4UMSrX+DNv7GTzEETHxQ83quiqp4bSaHRtr+tzNLyyupadj23sbm1vZPf3avpMFYcqjyUoWq4TIMUAVRRoIRGpID5roS6O7ia+PV7UFqEwR0OI2j7rBcIT3CGRurkD6NxC+EBE1egpqE3Gl937FRiHoIadfJFu2RPQReJk5IiSVHp5L9a3ZDHPgTIJdO66dgRthOmUHAJo1wr1hAxPmA9aBoaMB90O5m+MqJHRulSL1SmAqRT9fdEwnyth75rOn2GfT3vTcT/vGaM3mU7EUEUIwR8tsiLJcWQTnKhXaGAoxwawrgS5lbK+0wxbjLQOROCM//yIqmdlJzz0tntabFcSOPIkgNSIMfEIRekTG5IhVQJJ4/kmbySN+vJerHerY9Za8ZKZ/bJH1ifP9Qwm4g=</latexit>

pbits of E0after

<latexit sha1_base64="Msr477+DdE9Fp0lqkk/8wM2qPvc=">AAACFHicbVDLSgNBEJz1GeMr6tHLYhAUMeyKr6PgxZsRjArZGHonnThkZneZ6RXDsv6DF3/FiwdFvHrw5t84iTn4Khgoqrp7qAoTKQx53oczMjo2PjFZmCpOz8zOzZcWFs9MnGqONR7LWF+EYFCKCGskSOJFohFUKPE87B72/fNr1EbE0Sn1Emwo6ESiLTiQlZqljUABXXGQ2XG+FnRAKbjMNrfy9duA8IYyjQnas3bW5M1S2at4A7h/iT8kZTZEtVl6D1oxTxVGxCUYU/e9hBoZaBJcYl4MUoMJ8C50sG5pBApNIxuEyt1Vq7Tcdqzti8gdqN83MlDG9FRoJ/sRzG+vL/7n1VNq7zcyESUpYcS/Pmqn0qXY7TfktoRGTrJnCXBts3OXX4EGTrbHoi3B/x35Lznbqvi7lZ2T7fLByrCOAltmK2yN+WyPHbAjVmU1xtkde2BP7Nm5dx6dF+f1a3TEGe4ssR9w3j4BJSGfcg==</latexit>

O(2) repetitions

(d)

<latexit sha1_base64="/bqBi5foJO4uv+9jmoKRmqqhUbI=">AAACB3icdVBNS8NAEN34WetX1aMgi0XwFLbWGI8FLx4rWBXaUCbbTbu4m4TdjVJCb178K148KOLVv+DNf+OmraCiDwYe780wMy9MBdeGkA9nZnZufmGxtFReXlldW69sbF7oJFOUtWgiEnUVgmaCx6xluBHsKlUMZCjYZXh9UviXN0xpnsTnZpiyQEI/5hGnYKzUrex0+iAldHM+6ijeHxhQKrnFUzXqVqrErRPf9z1MXO/QI15BfP/IqxNcc8kYVTRFs1t57/QSmkkWGypA63aNpCbIQRlOBRuVO5lmKdBr6LO2pTFIpoN8/McI71mlh6NE2YoNHqvfJ3KQWg9laDslmIH+7RXiX147M9FxkPM4zQyL6WRRlAlsElyEgntcMWrE0BKgittbMR2AAmpsdGUbwten+H9yceDWjlzv7LDa2J3GUULbaBftoxryUQOdoiZqIYru0AN6Qs/OvfPovDivk9YZZzqzhX7AefsEN9qaGg==</latexit>

i!f

<latexit sha1_base64="n1OMryLl3FLdxXergVmgCPZ0B1Q=">AAACA3icdVDLSgNBEJz1bXxFvellSBA8LRPjuh4FL55EwTwgCWF20tHB2QczvWJYIl78FS8eFPHqT3jzb5ysEVS0oKGo6qa7K0iUNMjYuzMxOTU9Mzs3X1hYXFpeKa6u1U2cagE1EatYNwNuQMkIaihRQTPRwMNAQSO4PBz5jSvQRsbRGQ4S6IT8PJJ9KThaqVvcOO5mEkEPb9oI15jz3DLDbrHM3Crzfd+jzPV2PeaNiO/veVVGKy7LUSZjnHSLb+1eLNIQIhSKG9OqsAQ7GdcohYJhoZ0aSLi45OfQsjTiIZhOlv8wpFtW6dF+rG1FSHP1+0TGQ2MGYWA7Q44X5rc3Ev/yWin29zuZjJIUIRKfi/qpohjTUSC0JzUIVANLuNDS3krFBddc2CRMwYbw9Sn9n9R33Mqe653ulg9K4zjmyCYpkW1SIT45IEfkhNSIILfknjySJ+fOeXCenZfP1glnPLNOfsB5/QA3vpkc</latexit>

Niter iterations

<latexit sha1_base64="UCG8b3XtXacsKordCAxeifhf6k8=">AAACAXicbVDLSsNAFL3xWesr6kZwM7QILqQkouiy4MZlFfuAJoTJdNIOnTyYmQglxI2/4saFIm79C3f+jZM2C209cOFwzr3ce4+fcCaVZX0bS8srq2vrlY3q5tb2zq65t9+RcSoIbZOYx6LnY0k5i2hbMcVpLxEUhz6nXX98XfjdByoki6N7NUmoG+JhxAJGsNKSZx46IVYjgnl2l3uZ0xoxL7NOWZ57Zt1qWFOgRWKXpA4lWp755QxikoY0UoRjKfu2lSg3w0IxwmledVJJE0zGeEj7mkY4pNLNph/k6FgrAxTEQlek0FT9PZHhUMpJ6OvO4l457xXif14/VcGVm7EoSRWNyGxRkHKkYlTEgQZMUKL4RBNMBNO3IjLCAhOlQ6vqEOz5lxdJ56xhXzSs2/N6s1bGUYEjqMEJ2HAJTbiBFrSBwCM8wyu8GU/Gi/FufMxal4xy5gD+wPj8AbAjlu8=</latexit>

R0,i

<latexit sha1_base64="goPRBom/d9r4JFjJuyjfOIeKoME=">AAACAXicbVBNS8NAEJ3Ur1q/ol4EL6FF8CAlEUWPBS8eK5i20ISw2W7bpZtN2N0IJcSLf8WLB0W8+i+8+W/ctDlo64OBx3szzMwLE0alsu1vo7Kyura+Ud2sbW3v7O6Z+wcdGacCExfHLBa9EEnCKCeuooqRXiIIikJGuuHkpvC7D0RIGvN7NU2IH6ERp0OKkdJSYB55EVJjjFjm5kHmtcc0yOwzmueB2bCb9gzWMnFK0oAS7cD88gYxTiPCFWZIyr5jJ8rPkFAUM5LXvFSSBOEJGpG+phxFRPrZ7IPcOtHKwBrGQhdX1kz9PZGhSMppFOrO4l656BXif14/VcNrP6M8SRXheL5omDJLxVYRhzWggmDFppogLKi+1cJjJBBWOrSaDsFZfHmZdM6bzmXTvrtotOplHFU4hjqcggNX0IJbaIMLGB7hGV7hzXgyXox342PeWjHKmUP4A+PzB7TZlvI=</latexit>

U0,i

<latexit sha1_base64="J5II5MlJblkApiLP6mlBaAZ8VxM=">AAAB9XicbVBNS8NAEJ34WetX1aOXpUXwVBJR9Fjw4rGC/YA2lsl20y7dbMLuRimx/8OLB0W8+l+8+W/ctjlo64OBx3szzMwLEsG1cd1vZ2V1bX1js7BV3N7Z3dsvHRw2dZwqyho0FrFqB6iZ4JI1DDeCtRPFMAoEawWj66nfemBK81jemXHC/AgHkoecorHS/ZPbVSgHgvUyxEmvVHGr7gxkmXg5qUCOeq/01e3HNI2YNFSg1h3PTYyfoTKcCjYpdlPNEqQjHLCOpRIjpv1sdvWEnFilT8JY2ZKGzNTfExlGWo+jwHZGaIZ60ZuK/3md1IRXfsZlkhom6XxRmApiYjKNgPS5YtSIsSVIFbe3EjpEhdTYoIo2BG/x5WXSPKt6F1X39rxSK+dxFOAYynAKHlxCDW6gDg2goOAZXuHNeXRenHfnY9664uQzR/AHzucPqWiShA==</latexit>

|0iaa

<latexit sha1_base64="QB6/dwsnwOyWowRml+N8/qcI6gw=">AAAB9XicbVBNS8NAEJ34WetX1aOXpUXwVBJR9Fjw4rGC/YA2ls120i7dbMLuRimx/8OLB0W8+l+8+W/ctjlo64OBx3szzMwLEsG1cd1vZ2V1bX1js7BV3N7Z3dsvHRw2dZwqhg0Wi1i1A6pRcIkNw43AdqKQRoHAVjC6nvqtB1Sax/LOjBP0IzqQPOSMGivdP7ldReVAYC8LcNIrVdyqOwNZJl5OKpCj3it9dfsxSyOUhgmqdcdzE+NnVBnOBE6K3VRjQtmIDrBjqaQRaj+bXT0hJ1bpkzBWtqQhM/X3REYjrcdRYDsjaoZ60ZuK/3md1IRXfsZlkhqUbL4oTAUxMZlGQPpcITNibAllittbCRtSRZmxQRVtCN7iy8ukeVb1Lqru7XmlVs7jKMAxlOEUPLiEGtxAHRrAQMEzvMKb8+i8OO/Ox7x1xclnjuAPnM8fsQKSiQ==</latexit>

|0ibe

|0isys

(b)

<latexit sha1_base64="SDfuJs62KeDoMDKZRIAQulLk/RI=">AAAB/nicbVDLSsNAFJ3UV62vqLhyE1oEVyURRZcFN66kgn1AE8NketMOnUzCzEQoIeCvuHGhiFu/w51/46TNQlsPXO7hnHuZOydIGJXKtr+Nysrq2vpGdbO2tb2zu2fuH3RlnAoCHRKzWPQDLIFRDh1FFYN+IgBHAYNeMLku/N4jCEljfq+mCXgRHnEaUoKVlnzzCB4y6iZj6me3ftFzt01z32zYTXsGa5k4JWmgEm3f/HKHMUkj4IowLOXAsRPlZVgoShjkNTeVkGAywSMYaMpxBNLLZufn1olWhlYYC11cWTP190aGIymnUaAnI6zGctErxP+8QarCKy+jPEkVcDJ/KEyZpWKryMIaUgFEsakmmAiqb7XIGAtMlE6spkNwFr+8TLpnTeeiad+dN1r1Mo4qOkZ1dIocdIla6Aa1UQcRlKFn9IrejCfjxXg3PuajFaPcOUR/YHz+AK2Cldg=</latexit>

eiN⇧

<latexit sha1_base64="OBJj1WlatwgPFft4ov+PdyABmx8=">AAACB3icbVDLSsNAFJ3UV62vqEtBhhahbkoiii4LblxWsQ9oQphMJ+3QyUyYmQgldOfGX3HjQhG3/oI7/8ZJm4W2HrhwOOde7r0nTBhV2nG+rdLK6tr6RnmzsrW9s7tn7x90lEglJm0smJC9ECnCKCdtTTUjvUQSFIeMdMPxde53H4hUVPB7PUmIH6MhpxHFSBspsI+9GOkRRiy7mwaZ11I0cKZ1jySKMsFPA7vmNJwZ4DJxC1IDBVqB/eUNBE5jwjVmSKm+6yTaz5DUFDMyrXipIgnCYzQkfUM5ionys9kfU3hilAGMhDTFNZypvycyFCs1iUPTmV+tFr1c/M/rpzq68jPKk1QTjueLopRBLWAeChxQSbBmE0MQltTcCvEISYS1ia5iQnAXX14mnbOGe9Fwbs9rzWoRRxkcgSqoAxdcgia4AS3QBhg8gmfwCt6sJ+vFerc+5q0lq5g5BH9gff4ADbqZUA==</latexit>

R 0(✏)

-1

R™0(≤)

≤

<latexit sha1_base64="fqN4ZUiIAM488FcEiLPe7FCqYzA=">AAAB+XicbVBNS8NAEJ3Ur1q/oh69LC2Cp5KIoseCF48V7Ac0MWy2m3bpZhN2N4US8k+8eFDEq//Em//GbZuDtj4YeLw3w8y8MOVMacf5tiobm1vbO9Xd2t7+weGRfXzSVUkmCe2QhCeyH2JFORO0o5nmtJ9KiuOQ0144uZv7vSmViiXiUc9S6sd4JFjECNZGCmybPuXMS8csyJ3Ca7MisBtO01kArRO3JA0o0Q7sL2+YkCymQhOOlRq4Tqr9HEvNCKdFzcsUTTGZ4BEdGCpwTJWfLy4v0LlRhihKpCmh0UL9PZHjWKlZHJrOGOuxWvXm4n/eINPRrZ8zkWaaCrJcFGUc6QTNY0BDJinRfGYIJpKZWxEZY4mJNmHVTAju6svrpHvZdK+bzsNVo1Uv46jCGdThAly4gRbcQxs6QGAKz/AKb1ZuvVjv1seytWKVM6fwB9bnD5+vk4w=</latexit>

ei0⇧

<latexit sha1_base64="s5Zra+yZTD7s5JIFkh94sBwFM+0=">AAAB+HicbVDLSgNBEOz1GeMjqx69DAmCp7Arih4DXjxGMA9I1mV20psMmX0wMyvEJV/ixYMiXv0Ub/6Nk2QPmljQUFR1090VpIIr7Tjf1tr6xubWdmmnvLu3f1CxD4/aKskkwxZLRCK7AVUoeIwtzbXAbiqRRoHATjC+mfmdR5SKJ/G9nqToRXQY85Azqo3k2xV8yHk/HXHfJf0mn/p2zak7c5BV4hakBgWavv3VHyQsizDWTFCleq6Tai+nUnMmcFruZwpTysZ0iD1DYxqh8vL54VNyapQBCRNpKtZkrv6eyGmk1CQKTGdE9UgtezPxP6+X6fDay3mcZhpjtlgUZoLohMxSIAMukWkxMYQyyc2thI2opEybrMomBHf55VXSPq+7l3Xn7qLWqBZxlOAEqnAGLlxBA26hCS1gkMEzvMKb9WS9WO/Wx6J1zSpmjuEPrM8fLLGSqw==</latexit>

ei1⇧

(c)

<latexit sha1_base64="aHkUGwHvw0V5gfkj6nN/DYau1Zs=">AAACEXicbVDLSsNAFJ3UV62vqEs3Q4vQjSURRZcFN3VXwbSFNoTJdNIOnUnCzEQoIb/gxl9x40IRt+7c+TdO2lC09cDAuefcy9x7/JhRqSzr2yitrW9sbpW3Kzu7e/sH5uFRR0aJwMTBEYtEz0eSMBoSR1HFSC8WBHGfka4/ucn97gMRkkbhvZrGxOVoFNKAYqS05Jn1AUdqjBFLncxLF0UrOxvwZFHeZpln1qyGNQNcJXZBaqBA2zO/BsMIJ5yECjMkZd+2YuWmSCiKGckqg0SSGOEJGpG+piHiRLrp7KIMnmplCINI6BcqOFN/T6SISznlvu7Md5TLXi7+5/UTFVy7KQ3jRJEQzz8KEgZVBPN44JAKghWbaoKwoHpXiMdIIKx0iBUdgr188irpnDfsy4Z1d1FrVos4yuAEVEEd2OAKNEELtIEDMHgEz+AVvBlPxovxbnzMW0tGMXMM/sD4/AEP0J5R</latexit>

UHµI

FIG. 1. Circuit diagrams and schematic visualizations for estimating the ground state energy E0of a Hamiltonian Hwith a

near-optimal ground state preparation technique using amplitude ampliﬁcation. (a) An energy estimation circuit like the one

in the reference implementation under consideration [10] in which the probability of correctly measuring E0in a single round

is γ2. The value of γis determined by details of Usp(H). (b) A circuit that implements Usp by ﬁrst preparing an initial guess

|Φ0,iiand then running Niter rounds of AA in which the reﬂector about |Φ0,ii(RΦ0,i ) is straightforward to implement and the

reﬂector about |Ψ0i(RΨ0()) requires the use of quantum signal processing, as proposed in Ref. [7], to produce |Φ0,f i.Niter is

determined by γiand the desired ﬁnal overlap γf. The former overlap might vanish exponentially in the size of sys. (c) A circuit

that uses quantum signal processing to implement an -approximation to a degree-Nφpolynomial that suppresses support on

energy eigenstates above a known lower bound (µ), in favor of support on energy eigenstates below µ. The phases are chosen

using the method in Ref. [44]. (d) An illustration of the -approximate reﬂector, RΨ0(), and how it acts on eigenstates above

and below the energy gap ∆. Here, the calculated phases realize an approximation that clearly outperforms the target = 0.3.

titular question. Even in a scenario where γivanishes

exponentially with increasing n, there are parameter

regimes where there is a robust near-quadratic speedup

for better state preparation. This is consistent with

the Grover-like speedup [45] that one would expect [46],

though we note that we are exploring this in terms of

T-gate counts as a proxy for runtime, instead of query

complexity or some other more abstract quantiﬁer.

Methods.— Circuit diagrams that illustrate the imple-

mentation costs being studied are provided in Fig. 1. The

quantum computer that runs these circuits consists of

four registers: (sys) the n-qubit system register that en-

codes |Φ0,ii, (qpe) the auxiliary register that encodes p

bits of an estimate for E0, (aa) which implement ampli-

tude ampliﬁcation (AA), and (be) which block encode H.

In what follows, we describe the structure of the circuits

in Fig. 1and any attendant assumptions. Many details

that were originally elaborated elsewhere in the literature

are summarized in the Supplemental Materials (SM) [47].

For QPE, we use the highly optimized implementation

of Babbush et al. [10]. We indicate the Tcount asso-

ciated with estimating E0with Holevo variance ∆Eas

TQP E (∆E) and note that more relevant details can be

found in the SM [47]. We assume a particularly simple

approach to estimating E0. Each repetition of the circuit

will sample an eigenvalue from the spectrum of Hwith

probability proportional to the overlap of the input state

state with the associated eigenstate. So after O(γ−2) rep-

etitions the smallest observed eigenvalue will likely be E0.

We now derive conditions under which boosting γ2with

AA will reduce the expected total runtime for estimating

E0relative to only relying on UΦ0,i , the cost of which we

will denote TΦ0,i (see Fig. 1(b)).

AA consists of Niter applications of a product of two

reﬂections (RΦ0,i ,RΨ0) that boosts the overlap of the

state in sys to γf.Niter is determined by γi,

Niter =1

2sin−1γf

sin−1γi−1.(1)

While implementing RΦ0,i only requires controlled ap-

plications of UΦ0,i , the implementation of RΨ0is compli-

cated by |Ψ0igenerally being unknown. We will follow

Ref. [7] and construct an -approximation to this reﬂector

using quantum signal processing (QSP) [48], RΨ0() (see

Fig. 1(c)). This is a degree-Nφpolynomial in (H − µI)

that approximates a function that is ideally −1 for states

with energy less than µ−∆/2 and ideally 1 for states with

energy greater than µ+ ∆/2. Details pertaining to the

calculation of µand ∆ are included in the SM [47].

However, in practice each eigenvalue of RΨ0() is only

-close to {−1,+1}and RΨ0() is not an exact reﬂector.

One of the technical advances in this Letter is a bound on

such that the QSP circuit produces |Φ0,f iwith γf≥γi,

≤1−γ2

f/6N2

iter.(2)

A proof can be found in the SM [47]. The cost of imple-

menting the entire AA circuit is denoted TAA(γi, γf).

The only remaining details for the implementation un-

der consideration pertain to the block encoding of H[40].

Block encoding is used both to encode the eigenspectrum

of H, as sampled in QPE, and to implement a polyno-

mial in (H − µI) in QSP. As many of the details are

model-speciﬁc and extensively developed in other work,

we relegate a detailed discussion of block encoding to the

SM [47]. While there are alternatives to block encoding,

we leave it to future work to consider variants on the ap-

proach in Fig. 1making use of, e.g., Trotterized Hamilto-

nian evolution, either for encoding the eigenspectrum of

Hfor QPE or for implementing time-dependent Hamil-

tonian evolution in adiabatic state preparation [49].

With all of the components of our implementation

speciﬁed, we can prepare Tcounts for the circuits with

and without AA. The ratio of these counts deﬁnes the

improvement,

ι=γ−2

i(TΦ0,i +TQP E (∆E))

γ−2

f(TΦ0,i +TQP E (∆E) + TAA(γi, γf)) .(3)

Here the cost of AA is

TAA =NiterTRΦ0,i +Nφ(TUH+TeiφΠ).(4)

TRΦ0,i involves two applications of UΦ0,i and a single

multi-controlled Xgate. TUHis the cost of a single appli-

cation of the block-encoded Hamiltonian. TeiφΠinvolves

two multi-controlled Xgates and a single-qubit rotation

with angles determined using the protocol in Ref. [44].

Nφis the number of phases used to implement RΨ0()

and all parameter values will be chosen to saturate their

bounds. We note that Eq. 4depends on the rotation syn-

thesis error incurred in implementing the Hamiltonian

block encoding and the controlled rotations in QSP, and

the error analysis used in deriving our results is consid-

ered in the SM [47]. We consider better state preparation

as being worthwhile when ι > 1.

Results.— We ﬁrst consider resource estimates for the

1D transverse ﬁeld Ising model (TFIM) [50] with periodic

boundary conditions [51]. sys is encoded such that each

of the nqubits represents one of the Lsites. We consider

a simple form for UΦ0,i in which Ryrotations are applied

to each qubit to generate a product state. We tune the

rotation angles to construct a |Φ0,iiwith a target value

of γi. While not a particularly sophisticated choice for

initializing sys, it suﬃces for our purposes. We select 

to saturate the bound in Eq. 2with a target γ2

f= 0.75,

and assume that the true ﬁnal overlap is also γ2

f= 0.75;

a presentation of the diﬀerence between the target and

true overlaps can be found in Fig. 3.

10−510−410−310−210−1

γ2

10−1

100

101

102

103

∆E= 10−2

∆E= 10−1

L= 4

L= 16

L= 64

10−1

10−3

10−5

γ2

106

109

1012

TAA(γi, γf)

FIG. 2. Tcounts and improvement ιfor TFIM with L= 4,

16, and 64 sites, with saturating the bound in Eq. 2with γ2

= 0.75, γ2

iranging from 10−5to 10−1, and two diﬀerent values

of ∆E. The inset shows TAA and the main ﬁgure is a plot

of the improvement ιwith solid lines ﬁt to the asymptotic

form Eq. 5. The dashed line is a guide for the eye at ι=

1, above which improvement is seen when conducting state

preparation.

In Fig. 2we present ιand TAA for the TFIM as a func-

tion of L,γi, and ∆E. We ﬁnd ι > 1 for all instances

with γ2

i≤10−3, and even for larger γifor the higher

accuracy calculation. For γi1, the costs of QPE and

AA are both dominated by repeated applications of the

block-encoded Hamiltonian, leading to a simple approx-

imate form of ι

ι∼γ2

γ2

i ∆

∆E

sin−1γf

γi

log γ−2

i!,(5)

consistent with a near-quadratic Grover-like speedup in

γifrom AA. Importantly, the asymptotic improvement

has no explicit dependence on the system size, with the

only system size dependence in the ﬁnite-size error of

∆. We ﬁnd that our computed ιfollows this asymptotic

trend closely for ι≤10−2. We note that 88 logical qubits

are required for the L= 64 calculation with ∆E= 10−2,

with a detailed analysis of qubit counts in the SM [47].

To test the performance of our Usp(H) implementation,

we explicitly simulate circuits for L= 2,4,6 site TFIM

using the upper bound on in Eq. 2. For each Lwe run

nine simulations, with γ2

f= 0.9, 0.99 and 0.999, and γi

chosen such that Niter = 4, 6, 10. We are then able to

compare the values of γ2

factually realized in the simu-

lation to the speciﬁed value of γ2

fin Fig. 3. Noise-free

simulations were carried out using the PyTKET pack-

age [52] with the full source available in the SM [47].

100

10−2

10−4

10−6

Target 1 −γ2

100

10−2

10−4

10−6

Simulated 1 −γ2

L=2

L=4

L=6

FIG. 3. Comparison of the target γfand simulated γf

for the transverse ﬁeld Ising model with L= 2, 4, and 6

sites. For each value of L, state-vector simulations of the

full Usp(H) circuit were carried out for three target values,

1−γ2

f= 10−1,10−2,10−3, and three values of γisatisfying

Niter = 4,6,10. The black line is the x=yreference and our

results are consistent with the validity of the bound in Eq. 2.

We ﬁnd that the simulated inﬁdelity, 1 −γ2

f, is con-

sistently one or two orders of smaller than the target,

indicating that our bound for in Eq. 2could be ad-

justed to potentially realize further savings in implement-

ing this approach to state preparation. However, the

impact of on ιis only logarithmic, so removing this

looseness will only aﬀect our results by a small constant

factor. As such, we are conﬁdent that our conclusions

are not skewed by a loose bound in the state preparation

Tcounts.

Next, we consider resource estimates for a more realis-

tic and technologically important Hamiltonian. The solid

electrolyte β-alumina is known for its high ionic conduc-

tivity [53,54] and there is broad general interest in using

it for low-carbon energy storage [55]. Of particular in-

terest for these applications is the accurate calculation

of equilibrium voltage, ionic mobility, and thermal sta-

bility, which are all directly related to accurate ground

state energies of the battery as outlined by Delgado et al.

in their work on the lithium-ion battery Li2FeSiO4[56].

Classical computation of accurate ground state en-

ergies of the β-aluminas is challenged by the non-

stoichiometric chemical composition, Na1+xAl11O17+x/2,

which requires large supercells to resolve ﬁnite-size ef-

fects. This is a larger supercell than has been considered

in other resource estimates of materials. We choose this

particular example because it is large enough that mean-

10−510−410−310−210−1

γ2

10−1

100

101

102

103

104

∆E= 13 meV

∆E= 130 meV

N= 103

N= 105

N= 107

10−510−310−1

γ2

1014

1017

1020

TAA(γi, γf)

FIG. 4. Tcounts and improvement ιfor β-alumina structure

Na4Al22O35 with η= 610, N= 103,105,107, with sat-

urating the bound in Eq. 2with γ2

f= 0.75, γiranging from

10−5to 10−1and two diﬀerent values of ∆E. The inset shows

TAA for various system sizes, with the main ﬁgure presenting

ιwith solid lines ﬁt to the asymptotic form Eq. 5. The dashed

line is a guide for the eye at ι= 1.

ﬁeld classical heuristics (e.g., density functional theory)

are likely to be the only methods that are viable, poten-

tially leading to small values of γi. However, an analysis

of the precise value of γithat is classically achievable

with these heuristics is beyond the scope of this Letter

and thus we leave it as a free parameter.

In Fig. 4we present resource estimates for a

Na4Al22O35 supercell with 610 electrons using a ﬁrst

quantized representation [12,57] of the electronic struc-

ture Hamiltonian in a plane-wave basis set with cardinal-

ity N. We ﬁnd that ι > 1 in all cases where γ2

i≤10−2,

from small to large basis sets, and for ∆Ebelow chemi-

cal accuracy to diﬀerent extents. We also see that the T

counts for AA are such that it is plausible to imagine im-

plementing calculations like this on fault-tolerant quan-

tum computers that are perhaps a generation beyond the

ones considered in Refs. [10,11]. Even when starting with

a fairly large γ2

i= 0.1, we still ﬁnd an order of magnitude

improvement in T counts for a high accuracy calculation,

as a result of investing resources in better state prepa-

ration. We note that 33,275 logical qubits are required

for the N= 107calculation with ∆E= 13 meV; 18,635

logical qubits for anti-symmetrization and 14,640 logical

qubits for all other computations. A detailed analysis of

qubit counts is relegated to the SM [47], as well as the

full source code for computing resource estimates.

Conclusions.— We have developed resource estimates

for end-to-end ground state energy determination us-

ing near-optimal state preparation [7]. The ratio of

the Tcount for successful ground state energy estima-

tion, without and with this state preparation, deﬁne

an improvement factor that is related to likely runtime

reductions. This improvement is near-quadratic in γi

and demonstrated credible multiple-order-of-magnitude

speedups for a toy problem and a highly realistic elec-

tronic structure problem.

Future work will involve determining more realistic es-

timates for scenarios under which these types of speedups

will be realized. In particular, categorizing the values

of γitypical of classical heuristics that are eﬃciently

implementable as UΦ0,i is an open research area. It

also remains unclear whether eﬃcient implementations

of adiabatic state preparation or other variants on ﬁlter-

based state preparation are more or less eﬃcient than

the one examined in this Letter. Finally, whether quan-

tum phase estimation protocols with built-in tolerance

to state preparation errors [33,58] can be exploited to

achieve better improvements is a topic for future work.

Note added.— Between uploading the ﬁrst and second

versions of this Letter to the arXiv, we became aware of

another manuscript considering similar aspects of ground

state preparation [59].

We gratefully acknowledge useful conversations with

Ryan Babbush, Anand Ganti, Lucas Kocia, Alina

Kononov, Michael Kreshchuk, Andrew Landahl, Lin Lin,

Alicia Magann, Jonathan Moussa, Setso Metodi, Mason

Rhodes, and Norm Tubman. All authors were supported

by the National Nuclear Security Administration’s Ad-

vanced Simulation and Computing Program. AER was

partially supported by the U.S. Department of Energy,

Oﬃce of Science, Oﬃce of Advanced Scientiﬁc Comput-

ing Research, Quantum Computing Application Teams

program. ADB was partially supported by the U.S. De-

partment of Energy, Oﬃce of Science, National Quantum

Information Science Research Centers program and San-

dia National Laboratories’ Laboratory Directed Research

and Development program (Project 222396).

This article has been co-authored by employees of

National Technology & Engineering Solutions of San-

dia, LLC under Contract No. DE-NA0003525 with the

U.S. Department of Energy (DOE). The authors own all

right, title and interest in and to the article and are

solely responsible for its contents. The United States

Government retains and the publisher, by accepting the

article for publication, acknowledges that the United

States Government retains a non-exclusive, paid-up, ir-

revocable, world-wide license to publish or reproduce

the published form of this article or allow others to do

so, for United States Government purposes. The DOE

will provide public access to these results of federally

sponsored research in accordance with the DOE Pub-

lic Access Plan https://www.energy.gov/downloads/

doe-public-access-plan.

[1] S. Lloyd, Science 273, 1073 (1996).

[2] A. Aspuru-Guzik, A. D. Dutoi, P. J. Love, and M. Head-

Gordon, Science 309, 1704 (2005).

[3] S. P. Jordan, K. S. Lee, and J. Preskill, Science 336,

1130 (2012).

[4] D. Poulin and P. Wocjan, Physical review letters 102,

130503 (2009).

[5] N. M. Tubman, C. Mejuto-Zaera, J. M. Epstein, D. Hait,

D. S. Levine, W. Huggins, Z. Jiang, J. R. McClean,

R. Babbush, M. Head-Gordon, et al., arXiv preprint

arXiv:1809.05523 (2018).

[6] Y. Ge, J. Tura, and J. I. Cirac, Journal of Mathematical

Physics 60, 022202 (2019).

[7] L. Lin and Y. Tong, Quantum 4, 372 (2020).

[8] J. Lemieux, G. Duclos-Cianci, D. S´en´echal, and

D. Poulin, Physical Review A 103, 052408 (2021).

[9] M. Reiher, N. Wiebe, K. M. Svore, D. Wecker, and

M. Troyer, Proceedings of the national academy of sci-

ences 114, 7555 (2017).

[10] R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. Mc-

Clean, A. Paler, A. Fowler, and H. Neven, Physical Re-

view X 8, 041015 (2018).

[11] J. Lee, D. W. Berry, C. Gidney, W. J. Huggins, J. R.

McClean, N. Wiebe, and R. Babbush, PRX Quantum

2, 030305 (2021).

[12] Y. Su, D. W. Berry, N. Wiebe, N. Rubin, and R. Bab-

bush, PRX Quantum 2, 040332 (2021).

[13] Y. Su, H.-Y. Huang, and E. T. Campbell, Quantum 5,

495 (2021).

[14] V. von Burg, G. H. Low, T. H¨aner, D. S. Steiger, M. Rei-

her, M. Roetteler, and M. Troyer, Physical Review Re-

search 3, 033055 (2021).

[15] A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su,

Proceedings of the National Academy of Sciences 115,

9456 (2018).

[16] A. M. Childs and Y. Su, Physical review letters 123,

050503 (2019).

[17] M. C. Tran, Y. Su, D. Carney, and J. M. Taylor, PRX

Quantum 2, 010323 (2021).

[18] N. Klco and M. J. Savage, Physical Review A 99, 052335

(2019).

[19] H. Lamm, S. Lawrence, Y. Yamauchi, N. Collaboration,

et al.,Physical Review D 100, 034518 (2019).

[20] A. F. Shaw, P. Lougovski, J. R. Stryker, and N. Wiebe,

Quantum 4, 306 (2020).

[21] M. A. Nielsen and I. Chuang, “Quantum computation

and quantum information,” (2002).

[22] A. Y. Kitaev, A. Shen, and M. N. Vyalyi, Classical and

quantum computation, 47 (American Mathematical Soc.,

2002).

[23] J. Kempe, A. Kitaev, and O. Regev, SIAM journal on

computing 35, 1070 (2006).

[24] R. P. Feynman, International Journal of Theoretical

Physics 21, 467 (1982).

[25] B. O’Gorman, S. Irani, J. Whitﬁeld, and B. Feﬀerman,

PRX Quantum 3, 020322 (2022).

[26] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q.

Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’brien,

Nature communications 5, 1 (2014).

[27] P. J. O’Malley, R. Babbush, I. D. Kivlichan, J. Romero,

J. R. McClean, R. Barends, J. Kelly, P. Roushan,

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

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

10 玖币 0人已下载

立即下载

摘要：

QuantifyingT-gate-countimprovementsforground-state-energyestimationwithnear-optimalstatepreparationS.Pathak,1A.E.Russo,1S.K.Seritan,2andA.D.Baczewski11QuantumAlgorithmsandApplicationsCollaboratory,SandiaNationalLaboratories,AlbuquerqueNM,USA2QuantumAlgorithmsandApplicationsCollaboratory,SandiaNation...

展开>> 收起<<

Quantifying T-gate-count improvements for ground-state-energy estimation with near-optimal state preparation S. Pathak1A.E. Russo1S.K. Seritan2and A.D. Baczewski1.pdf

共24页,预览5页

还剩页未读，继续阅读

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

Quantifying T-gate-count improvements for ground-state-energy estimation with near-optimal state preparation S. Pathak1A.E. Russo1S.K. Seritan2and A.D. Baczewski1

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: