A Depolarizing Noise-aware Transpiler for Optimal Amplitude Amplification Preprint compiled November 29 2022

2025-04-30 1 0 4.53MB 14 页 10玖币
侵权投诉
A Depolarizing Noise-aware Transpiler for Optimal Amplitude
Amplification
Preprint,compiled November 29, 2022
Debashis Ganguly
Independent Researcher
DebashisGanguly@gmail.com
Wonsun Ahn
Department of Computer Science
University of Pittsburgh
wonsun.ahn@gmail.com
Abstract
Amplitude amplification provides a quadratic speed-up for an array of quantum algorithms when run on a
quantum machine perfectly isolated from its environment. However, the advantage is substantially diminished as
the NISQ-era quantum machines lack the large number of qubits necessary to provide error correction. Noise in
the computation grows with the number of gate counts in the circuit with each iteration of amplitude amplification.
After a certain number of amplifications, the loss in accuracy from the gate noise starts to overshadow the gain in
accuracy due to amplification, forming an inflection point. Beyond this point, accuracy continues to deteriorate
until the machine reaches a maximally mixed state where the result is uniformly random. Hence, quantum
transpilers should take the noise parameters of the underlying quantum machine into consideration such that the
circuit can be optimized to attain the maximal accuracy possible for that machine. In this work, we propose an
extension to the transpiler that predicts the accuracy of the result at every amplification with high fidelity by
applying pure Bayesian analysis to individual gate noise rates. Using this information, it finds the inflection
point and optimizes the circuit by halting amplification at that point. The prediction is made without needing to
execute the circuit either on a quantum simulator or an actual quantum machine.
1 Introduction
Lov Grover’s quantum search algorithm [9] has initially been
proposed for unstructured search problems, i.e., for finding a
marked element in a unstructured database with high probability.
However, today, its uses extend beyond that; as it can be used as
a general subroutine to obtain quadratic run time improvements
for a variety of other algorithms [2,6
–
8,13,15,18]. Although
Grover’s algorithm does not solve NP–complete problems in
polynomial time, the wide range of applications, that use it as a
subroutine more than compensates for this.
Amplitude amplification [3] is a generalization of the basic idea
behind Grover’s algorithm. At a high level, amplitude amplifica-
tion works in an iterative manner where, at each iteration, the
probability of the winning outcome is amplified. The probability
approaches one after
O
(
√N
) iterations, where
N
is the size of
the search space, leading to a quadratic speedup over classical
algorithms. Section 2.1 covers the mathematical foundation of
amplitude amplification in depth.
Today’s quantum processors are “noisy” and may lose their
quantum state due to quantum decoherence over time. More-
over, they do not have enough qubits to perform error correction
on the noise. These are the two defining characteristics of noisy
intermediate-scale quantum (NISQ) machines. Amplitude am-
plification involves repeating the oracle and diffuser circuits in
Figure 2iteratively. Hence. the total number of gates in the
circuit grows linearly with each iteration, and with it, gate noise.
After a certain number of iterations, loss in accuracy due to gate
noise trumps the gain in accuracy from amplitude amplification.
Most quantum machines currently are part of a cloud infras-
tructure where many machines with varying qubit numbers and
noise parameters are assembled as a shared resource. This is
done to amortize the cost of building and maintaining a quan-
tum infrastructure over many users. When users submit jobs
to the cloud, it is the responsibility of the job scheduler to find
an appropriate machine to run on, or reject the job if it is not
suitable for any machine. As of now, the only hard criterion
that the scheduler can use is the number of qubits. Hence, it
considers any machine with the requisite number of qubits to be
equally suitable. Machines do expose some noise parameters
to the scheduler such as gate noise rates for each physical gate
in the machine and thermal relaxation times; but there is no
framework which can help predict how those parameters will
affect the accuracy of the result.
We propose an extension to the transpiler, which converts a given
quantum algorithm to a quantum circuit for the given machine.
The purpose of the extension is to 1) given the transpiled circuit,
provide a prediction on the accuracy of the final outcome by
analyzing the circuit and applying the noise parameters to each
gate, and 2) optimize the transpiled circuit so that it reaches the
maximal accuracy that is possible on that machine, based on
that prediction. Armed with this information, the scheduler now
can assign a job to the machine that is most suitable for the job
and also be guaranteed that the job will be executed in the most
optimal way on that machine.
Our transpiler extension uses a Bayesian probabilistic model
to compute the probability of noise seeping into an amplifi-
cation iteration, analyzing the circuit using noise parameters
of single-qubit and two-qubit quantum gates advertised by the
quantum machine. It makes this estimation for every iteration
of an amplitude amplification loop. The accuracy measured at
every iteration initially increases due to amplitude amplification
but often displays an “inflection point” beyond which further
amplification cannot surmount the degrading effects of noise. If
an inflection point exists, the transpiler optimizes this circuit by
truncating the circuit at that point so that no more iterations are
performed.
arXiv:2210.14335v4 [quant-ph] 26 Nov 2022
Preprint –ADepolarizing Noise-aware Transpiler for Optimal Amplitude Amplification 2
Now, it is worth mentioning that the probability of noise-free
execution is not equivalent to the probability of the outcome
being accurate. That is because even noisy outcomes have the
potential to produce the winning result when measured. This is
true for noisy quantum systems as it is true for noisy classical
systems. However, we will show the probability of noise-free
execution is closely correlated to the accuracy of the result, such
that making a prediction based on the former still results in a
near optimal circuit.
In summary, we make the following contributions:
•
We make the empirical observation that there some-
times exists an inflection point beyond which further
amplification iterations result in losses in accuracy.
•
We propose novel intrinsics in the OpenQASM lan-
guage that delineates iterations in an iterative quantum
algorithm such as amplitude amplification and also
conveys the amplification achieved in each iteration.
•
We implement an extension to the circuit transpiler
that utilizes Bayesian probabilistic model to estimate
the depolarizing noise generated by the gates in the
iteration delineated by the intrinsics, in order to predict
the inflection point.
•
We demonstrate that the estimated probability of the
winning outcome(s) being noise-free follows closely
the probability of the result being winning outcome(s),
by actual measurements on quantum circuit. As a result,
we show that our prediction of the inflection point is
highly accurate.
2 Background
First, we will cover the necessary background on amplitude
amplification to give the readers a comprehensive perspective on
the iterative execution of quantum circuit to find a solution with
higher probability. Then, this section describes depolarizing
channel, one of the most common noise models in quantum
computing considered by real quantum resources.
2.1 Amplitude Amplification
Grover’s quantum search algorithm uses a procedure called
amplitude amplification, which is how a quantum computer
significantly enhances the probability of a solution state. This
procedure amplifies or stretches out the amplitude of the marked
item(s), which shrinks the amplitude of the other items, such
that measuring the final state will return the right item(s) with
near-certainty. This section explains the basic steps invoked by
Grover’s quantum search algorithm as part of amplitude ampli-
fication, highlighting the geometrical interpretation in terms of
two reflections, which generate a rotation in a two-dimensional
plane.
Grover’s algorithm is an example of an unstructured quantum
search where we wish to locate one item with a unique property
in a large list of
N
items. At the beginning, we have no idea
where the marked item is. Therefore, any guess of its location
is as good as any other, which can be expressed in terms of a
uniform superposition:
|si
=
1
√NPN−1
x=0|xi
, where the dimension
of the problem is
N
. If at this point we were to measure in the
standard basis
{|xi}
, this superposition would collapse, according
to the fifth quantum law, to any one of the basis states with the
same probability of
1
N
=
1
2n
, where
n
is the number of qubits to
compose the problem. Our chances of guessing the right value
is therefore 1 in 2
n
, as could be expected. Hence, on average
we would need to try about
N
2
=2
n−1
times to guess the correct
item by a classical algorithm.
Step 1: Initial superposition state.
The amplitude amplifica-
tion procedure starts out in the uniform superposition
|si
, which
is constructed from
|si
=
H⊗n|0in
. The left graphic in Figure 1a
corresponds to the two-dimensional plane spanned by perpen-
dicular vectors
|wi
and
|s0i
. This allows to express the initial
state as
|si
=
sin
(
θ
)
|wi
+
cos
(
θ
)
|s0i
, where
θ
=
arcsin
(
hs|wi
),
and
|wi
and
|s0i
are respectively the winner and an additional
state perpendicular to
|wi
obtained from
|si
by removing
|wi
and
rescaling.The right graphic in Figure 1a denotes a bar graph of
the amplitudes of the state |si.
Step 2: Conditional phase shift by oracle.
Next, the oracle
reflection
Uf
is applied to the state
|si
. This oracle, described
as
Uf|xi
=(
−
1)
f(x)|xi
, is a diagonal matrix, where the entry
that corresponds to the marked item, that we are searching for,
will have a negative phase. Geometrically this corresponds to a
reflection of the state
|si
about
|s0i
shown in the left graphic of
Figure 1b. This transformation means that the amplitude in front
of the state corresponding to the marked item becomes negative,
which in turn means that the average amplitude, indicated by a
dashed line in right graphic of Figure 1b has been lowered.
Step 3: Inversion about the mean by diffuser.
Next, the
diffuser circuit maps the winning state, corresponding to the
marked item, to
UsUf|si
.
Us
=2
|sihs| −
1 corresponds to an
additional rotation about the state
|si
. The two reflections by
Uf
and
Us
geometrically corresponds to a rotation, shown in
left graphic of Figure 1c, that brings the initial state
|si
closer
towards the winner
|wi
. Since the average amplitude has been
lowered by the first reflection,
Uf
, this transformation boosts
the negative amplitude of
|wi
to roughly three times its original
value, while it decreases the other amplitudes, as shown in the
right graphic of Figure 1c.
The procedure of amplitude amplification corresponds to the
combination of
Step 2
and
Step 3
, which will be repeated sev-
eral times (as shown in Figure 2) to zero in on the winner, i.e,
when
|si
overlaps on
|wi
. It turns out the number of iterations
required for this is
O
(
√N
) and thus providing a quadratic speed
up over a classical counterpart.
Grover’s algorithm uses Hadamard gates,
H⊗n|0in
to create the
uniform superposition of all the states at the beginning of the
Grover operator. If some information on the good states is avail-
able, it might be useful to not start in a uniform superposition but
only initialize specific states. Also, the diffusion operator does
not reflect about the equal superposition state, but another state
specified via an operator
A
, where
Q
=
AS0A†Sf
. This gen-
eralized version of Grover’s operator (
Q
) is known as Quantum
Amplitude Amplification [4].
2.2 Quantum Depolarizing Channel
In quantum information theory, a quantum channel is a com-
munication channel which can transmit quantum information,
as well as classical information. A quantum depolarizing chan-
Preprint –ADepolarizing Noise-aware Transpiler for Optimal Amplitude Amplification 3
(a) Initial superposition state
(b) Conditional phase shift by oracle
(c) Inversion about the mean
Figure 1: Geometrical representation of amplitude amplification.
Figure 2: Repetitive execution of quantum circuit for amplitude
amplification.
nel is a model for quantum noise in quantum systems. The
depolarizing channel can be viewed as a completely positive
trace-preserving map,
Eλ
(
ρ
), which maps a mixed state
ρ
onto a
linear combination of itself and the maximally mixed state and
can be defined as
Eλ(ρ)=(1 −λ)ρ+λT r[ρ]I
2n
with 0 ≤λ≤4n
4n−1
where,
λis the depolarizing error parameter
nis the number of qubits.
(1)
When
λ
=0,
Eλ
(
ρ
)=
ρ
, which is the identity channel and when
λ
=1,
Eλ
(
ρ
)=
I
2n
, which is a completely depolarizing channel
returning maximally mixed state.
Depolarizing channel is symmetrical across all three
x
,
y
, and
z
-axes. Hence,
Eλ
(
ρ
) can be interpreted as a uniform contraction
of the Bloch sphere, parameterized by
λ
. For example,
λ
=0
represents the complete contraction of the Bloch-sphere down
to the single-point I
2given by the origin.
The additivity of Holevo information for all channels was a fa-
mous open conjecture in quantum information theory, but it is
now known that this conjecture doesn’t hold in general. This
was proved by showing that the additivity of minimum output
entropy for all channels doesn’t hold [10], which is an equivalent
conjecture. Nonetheless, the additivity of the Holevo informa-
tion is shown to hold for the quantum depolarizing channel.
Christopher King [12] showed that the maximum output p-norm
of the depolarizing channel is multiplicative, which implied the
additivity of the minimum output entropy, which is equivalent
to the additivity of the Holevo information.
3 Motivation
This section motivates our research by presenting an empiri-
cal observation on how noise affects the outcome probability
of a marked item produced by a quantum algorithm running
amplitude amplification iteratively.
NISQ era quantum resources are far from perfect and riddled
with noises. Users can effectively query a quantum resource
to retrieve its properties such as noise parameters for different
quantum gates listed by their indices or positions. There are
two types of noise channels captured by these properties - (i)
depolarizing channel, and (ii) thermal relaxation times. In this
research, we focus on depolarizing channel alone. An important
fact to note here is that the value of noise parameters vary from
one position to another even for the same gate type. Table 2
lists the average value of quantum depolarizing noise parameters
over all indices of
sx
,
rz
, and
cx
gates present in an array of
popular IBMQ quantum resources [11]. Note the large vari-
ance not only in the number of supported qubits but also in the
noise parameters, making it hard for the scheduler to optimally
schedule jobs without a good predictor.
A
Z
-gate implements rotations around the
Z
axis which corre-
sponds to a change in the relative phase between the
|
0
i
and
|
1
i
states. A
Z
gate can be implemented by either detuning the
frequency of the qubit with respect to the drive field for some
finite amount of time or by composite
X
and
Y
gates. A
Z
gate,
implemented by adding a phase offset to the drive field for all
subsequent
X
and
Y
gates, is essentially perfect [16]. IBM Quan-
摘要：

ADepolarizingNoise-awareTranspilerforOptimalAmplitudeAmplificationPreprint,compiledNovember29,2022DebashisGangulyIndependentResearcherDebashisGanguly@gmail.comWonsunAhnDepartmentofComputerScienceUniversityofPittsburghwonsun.ahn@gmail.comAbstractAmplitudeamplicationprovidesaquadraticspeed-upforanarr...

展开>> 收起<<
A Depolarizing Noise-aware Transpiler for Optimal Amplitude Amplification Preprint compiled November 29 2022.pdf

共14页,预览3页

还剩页未读， 继续阅读

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

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：14 页 大小：4.53MB 格式：PDF 时间：2025-04-30

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 配电装置 动力学连接体 力的合成 高考理综 全宋诗作者索引 公务员考试
/ 14
评分 收藏
分享
立即下载
客服
关注