Deterministic quantum search with adjustable parameters implementations and applications Guanzhong Liand Lvzhou Li_2

2025-05-06 1 0 1.14MB 22 页 10玖币

侵权投诉

Deterministic quantum search with adjustable

parameters: implementations and applications

Guanzhong Li∗and Lvzhou Li†

Institute of Quantum Computing and Computer Theory,

School of Computer Science and Engineering,

Sun Yat-sen University, Guangzhou 510006, China

February 3, 2023

Abstract

Grover’s algorithm provides a quadratic speedup over classical algorithms to search

for marked elements in an unstructured database. The original algorithm is probabilistic,

returning a marked element with bounded error. There are several schemes to achieve the

deterministic version, by using the generalized Grover’s iteration G(α, β) := Sr(β)So(α)

composed of phase oracle So(α) and phase rotation Sr(β). However, in all the existing

schemes the value range of αand βis limited; for instance, in the three early schemes α

and βare determined by the proportion of marked states M/N. In this paper, we break

through this limitation by presenting a search framework with adjustable parameters,

which allows αor βto be arbitrarily given. The signiﬁcance of the framework lies not

only in the expansion of mathematical form, but also in its application value, as we present

two disparate problems which we are able to solve deterministically using the proposed

framework, whereas previous schemes are ineﬀective.

1 Introduction

1.1 Background

Grover’s algorithm [1] is one of the most fundamental algorithms in quantum computing, as it

provides a quadratic speedup for the unstructured search problem. In this problem, the user

is allowed to query an oracle, which outputs information about whether an element is marked,

after receiving the element index. In quantum computing, one may input superposition of

diﬀerent indexes to the oracle, and it will also output a superposition of answers. Grover’s

algorithm cleverly makes use of this characteristic and achieves quadratic speedup compared

to classical query-based search algorithms. It also works in the very general context, because

the oracle is regarded as a black box so that there need not be any promise on the structure

of the database. This black box feature makes it easy to generalize Grover’s algorithm to

quantum amplitude ampliﬁcation [2], which has become an important subroutine in designing

many other quantum algorithms.

Due to its great importance, research even just on Grover’s algorithm itself has never stopped

ever since it was proposed. One question is whether Grover’s algorithm can be made exact,

∗Email: ligzh9@mail2.sysu.edu.cn

†Email: lilvzh@mail.sysu.edu.cn (corresponding author)

arXiv:2210.12644v2 [quant-ph] 2 Feb 2023

as the original Grover’s algorithm can only output a marked element with a high probability,

but not with certainty. To this end, three methods [2,3,4] were proposed, which are based

on diﬀerent ideas but all, for the ﬁrst step, change the two phase ﬂip operations in the original

Grover’s algorithm to the following general operations:

So(α) = eiα ΠM,(1)

Sr(β) = e−iβ |ψ0ihψ0|.(2)

So(α) rotates the phase of the marked states by eiα, where ΠMrepresents orthogonal projector

onto the subspace spanned by marked states. Sr(β) rotates the phase of the initial state |ψ0i

(an equal-superposition of all indexes) by e−iβ. Note that when α=β=π, the generalized

Grover’s operation

G(α, β) := Sr(β)So(α) (3)

recovers to the original Grover’s iteration. A quantum circuit which realizes the generalized

Grover’s operation G(α, β) using twice the standard oracle Ofis shown in Fig. 1.









 

  

 

   

 







Figure 1: A quantum circuit to realize the generalized Grover’s operation G(α, β) =

Sr(β)So(α). The ﬁrst nhorizontal lines represents working qubits storing N= 2nelement

indexes, and the last line represents an ancillary qubit initially set to |0i. The standard oracle

Ofmaps |xi|bito |xi|b⊕f(x)i, where ⊕is the XOR operation, and the Boolean function

f(x) = 1 iﬀ xrepresents a marked element index. The vertical line with circles is the multiple

controlled-NOT gate which ﬂips the ancillary qubit whenever the ﬁrst nqubits are all |0i. Cor-

rectness of the circuit implementing So(α) can be easily veriﬁed by considering basis state |xi

when f(x) = 0 or 1 separately. Note that Sr(β) is equal to H⊗n(I−(1 −e−iβ )|0i⊗nh0|⊗n)H⊗n.

The three methods [2,3,4] then choose appropriate parameters α, β, k based on diﬀerent

ideas (which we summarize them as ‘big-small step’, ‘conjugate rotation’, and ‘3D rotation’),

so that after kiterations of G(α, β) to the initial state |ψ0i, an equal superposition of marked

states is produced, and measurement in the computational basis will lead to a marked state

with certainty. A summary of them is presented in Table 1.

Compared to the original Grover’s algorithm, the three methods produce a marked state

with certainty while maintaining the quadratic speedup (note that kopt ≈π

4qM

N), but they

require knowledge of the ratio λ=M/N. In fact, the ratio λis necessary to design quantum

exact search algorithm, as it has been proved in Ref. [5] that any quantum algorithm for exact

search without knowing the number Mof marked elements requires Nqueries (by reducing

the computation of Boolean function ORNto exact search, and proving the former requires N

queries to achieve certainty).

1.2 Contributions

As can be seen from Table 1, the parameters α, β in G(α, β) = Sr(β)So(α) are ﬁxed once the

ratio λis known. One question now naturally arises as follows.

method procedure k

big-small step [2]G(α1,−β1)Gk(π, π)|ψ0i bkoptc

conjugate rotation [3]Gk(α2,−β2)So(u)|ψ0i dkopte

3D rotation [4]Gk(α3,−α3)|ψ0i dkopte

Table 1: Three methods to achieve exact Grover search. Parameter kopt =π/2θ−1/2, where θ=

2 arcsin √λ, and λ=M/N is the proportion of marked elements. Parameters (α1, β1) satisfy

(are solution to) the complex valued equation “(−cos θ+icot α1

2) cot(2k+ 1)θ

2=eiβ1sin θ”.

Parameters (α2, β2) satisfy the equations “sin α2

2sin θ= sin π−θ

2k” and “tan β2

2= tan α2

2cos θ”.

Parameter u=π−β2

2. Parameter α3satisﬁes the equation “sin π

4k+2 = sin α3

2sin θ

2”.

The question: Is it possible to achieve exact search when one of the parameters α, β in G(α, β)

is arbitrarily given? Or to be more precise, when the angle αin phase oracle So(α), or the angle

βin phase rotation Sr(β)is arbitrarily given?

In this paper, we answer the above question aﬃrmatively. Speciﬁcally, we have the following

two theorems for the two cases in which αor βis arbitrarily given:

Theorem 1. Given the phase oracle So(α)with an arbitrary angle α∈(0,2π), whenever k >

klower, there always exits a pair of parameters (β1, β2), such that applying Fxr,α := G(α, β2)G(α, β1)

to |ψ0ifor ktimes will produce an equal superposition of marked states. The lower bound of k

klower =π



4 arcsin(√λsin α

2) mod [−π

2,π

2]



∈O(1/√λ),(4)

where λ∈(0,1) is the proportion of marked elements, and the notation “xmod [−π

2,π

2]” means

to add xwith an appropriate integer multiples lof π, such that x+lπ ∈[−π

2,π

2].

Theorem 2. Given the phase rotation Sr(β)with an arbitrary angle β∈(0,2π), when-

ever k > klower, there always exits a pair of parameters (α1, α2), such that applying Fxr,β :=

G(α1, β)G(α2, β)to |ψ0ifor ktimes will produce an equal superposition of marked states. The

lower bound of kis

klower =π



4 arcsin(√λsin β

2) mod [−π

2,π

2]



∈O(1/√λ).(5)

In Section 2, two applications of the above results will be presented. Here we have a look

at the proof outline.

Proof outline of Theorem 1and 2:The proof is divided into two parts:

1. To derive the explicit equations that parameters (k, β1, β2) or (k, α1, α2) need to satisfy.

This is done in Section 3with the ﬁnal equations shown by Eqs. (34),(35) for (k, β1, β2); and

Eqs. (36),(37) for (k, α1, α2). We ﬁrst determine the eﬀect of Fxr =G(α2, β2)G(α1, β1) in its

invariant subspace spanned by |Riand |Ti, which are the equal-superposition of unmarked

and marked states respectively. In fact, Fxr can be seen as a rotation R~n(φ) composing of

four rotations Sr(β2)So(α2)Sr(β1)So(α1) on the Bloch sphere of basis {|Ri,|Ti}, so we can

then calculate the rotation parameters ~n and φof Fxr,α and Fxr,β (Lemma 4). The Bloch

sphere interpretation of single-qubit operations provides us with the tool to deal with the

exponentiation Fk

xr, because of the equation Rk

~n(φ) = R~n(kφ). Then by considering the real

and imaginary part of 0 = hR|Fk

xr,α |ψ0ior 0 = hR|Fk

xr,β |ψ0i, we obtain the equations that

parameters (k, β1, β2) or (k, α1, α2) need to satisfy.

2. To prove that whenever kis greater than klower, there exists a solution (β1, β2) or (α1, α2)

to their corresponding equations. This part is quite technical and is shown in Section 4, where

we make use of 3D geometry (Lemma 6) and the intermediate value theorem of continuous

function on closed intervals. We only show the proof for the case where αis ﬁxed, since the

proof for βbeing ﬁxed is almost the same, but we point out some diﬀerences in Section 4.5.

Remark: We call the procedure in Theorem 1and 2the ﬁxed-axis-rotation (FXR) method,

because the exponentiation Fk

xr can be seen as rotating about a ﬁxed axis for ktimes on the

Bloch sphere. The peculiar notation in the denominator of Eq. (4) only takes eﬀect when λis

large, because when λis small, 4 arcsin(√λsin α

2) will always be in [0,π

2], and klower will be of

order O(1/√λ), maintaining the quadratic speedup. The same goes for Eq. (5).

1.3 Related work and paper structure

A special case of Theorem 1with α=πwas considered by Roy et al. in [6], where the

deterministic two-parameter (D2p) protocol was proposed. The D2p protocol obtains zero

failure rate by applying G(π, β1) and G(π, β2), alternatively, to the initial state |ψ0iuntil

k≥ dkopteoracle queries are made. When kis even, the last iteration is G(π, β2); when kis

odd, the last iteration is G(π, β1) and the equations which parameters (β1, β2) need to satisfy

are more complicated. Compared to the D2p protocol, our FXR method iterates Fxr as one

piece for ktimes, regardless of the parity of k, therefore only one system of equations needs to

be solved to obtain parameters (β1, β2). Moreover, they claimed that the equations can always

be solved when k>kopt and λ61/4, but lack rigorous proof.

The rest of this paper is organized as follows. We ﬁrst give two applications of our results

in Section 2. The ﬁrst uses Theorem 1and the other uses Theorem 2. In Section 3we describe

the intuition behind our FXR method, and derive the equations that parameters (k, β1, β2) or

(k, α1, α2) need to satisfy. In Section 4we prove the existence of solution (β1, β2) or (α1, α2) to

the corresponding equations whenever kis greater than klower. Conclusion and future work are

discussed in Section 5.

2 Applications

In this section, we present two applications of the search framework with adjustable parameters.

The ﬁrst uses Theorem 1, and the second uses Theorem 2. It can be seen especially from the

second application that the search framework can be deployed in designing quantum exact

algorithms no longer restricted to Grover search problem, and the key step is to reduce the

problem under consideration to the problem of transforming initial state to target state in a

two-dimensional subspace with some obtained G(α, β). We believe that the two applications

shown below are only tip of the iceberg demonstrating the usefulness of the search framework,

and that more interesting ones will be found in the future.

2.1 Identifying secret string exactly with Hamming distance oracle

Hunziker and Meyer [7] considered the problem of identifying a secret string s∈[k]n, by

querying the Hamming distance oracle hs(x) = dist(x, s) mod r, where r= max{2,6−k},

and dist(x, s) is the generalized Hamming distance between the query string xand s, i.e., the

number of components at which they diﬀer. When k∈ {2,3,4}, Algorithm B proposed in [7]

requires only one query to identify sexactly. However, the case of k > 4 is more complicated,

and we recall the main idea proposed in [7] for this case in the following, where the second step

has a ﬂaw and can be amended by using Theorem 1.

(i) Algorithm C proposed in [7] can be viewed as nsynchronous Grover search on each

position of s. In the i-th position, a Grover search with O(√k) iterations is performed for

ﬁnding one marked item out of kitems, and thus siis identiﬁed correctly with probability

at worst 1 −1

k[8]. As a result, the probability of identifying sis at least (1 −1

k)nwhich

is bounded above 1

2+when n < −kln(1

2+).

(ii) The Grover search on each position can be adjusted to succeed with probability 1 by

using one of the three methods in Table 1.

(iii) Thus, the condition n < −kln(1

2+) can be removed, which leads to a quantum algorithm

identifying swith certainty and consuming O(√k) queries.

Algorithm 1: Algorithm C in [7]

Input: An oracle Ohsfor s∈[k]nsuch that Ohs|xi|bi=|xi|b⊕hs(x)i.

Output: The secret string s.

Runtime: O(√k) queries to Ohs. Succeeds with probability at least 1

2+when

n < −kln(1

2+).

Procedure:

1Initial the state to |0i⊗n|0i ∈ (Ck)⊗n⊗C2.

2Apply the unitary transformation QF T ⊗n

k⊗(HX)

3for i=1:b1

2(π/(2 arcsin( 1

√k)) −1)edo

4apply the oracle Ohs.

5apply the unitary transformation (QF Tk(I−2|0ih0|)QF T †

k)⊗n⊗I

6end

7Measure the ﬁrst nregisters.

However, as pointed out in [9], the second item above is not true, that is, the algorithm

cannot be adjusted to succeed with probability 1 by using the three methods in Table 1. We

explain the reason below.

First note that when k > 4, we have hs(x) = (n−Pn

i=1 δsixi) mod 2, and the quantum

oracle works as Ohs|xi|bi=|xi|b⊕hs(x)iwhere ⊕denotes the bitwise XOR. More speciﬁcally,

the oracle Ohaworks as follows:

Ohs(|xi ⊗ |−i) = |xi ⊗ 1

√2(|0⊕hs(x)i−|1⊕hs(x)i) (6)

= (−1)hs(x)|xi ⊗ |−i (7)

= (−1)(n−Pn

i=1 δsixi) mod 2|xi ⊗ |−i (8)

= (−1)n−Pn

i=1 δsixi|xi ⊗ |−i (9)

= (−1)n

i=1

(−1)δsixi|xii ⊗ |−i,(10)

where |−i denotes the state 1

√2(|0i−|1i). The trick employed there is phase pick-back as shown

in Eq. (6) and Eq. (7), adding a ﬁxed phase −1 to |xiiwhen xiis equal to si. It should be

pointed out that Eq. (9) holds as (−1)l= (−1)lmod 2 for any 0 ≤l≤n, but it will not hold if

we replace −1 with eiφ for general φ, since eiφl =eiφl mod 2 no longer holds. On the other hand,

the three methods in Table 1requires the phase oracle So(α) to have arbitrary user-controllable

angle α. That is why the step in the second item above cannot be adjusted to succeed with

probability 1 by using the three methods in Table 1.

Nevertheless, we can use the FXR method instead, by setting the phase oracle’s angle α=π

and λ= 1/k in Theorem 1. We will then identify the secret string sby measuring the ﬁrst n

registers, and what’s more, the query complexity remains O(√k) by Eq. (4).

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

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

10 玖币 0人已下载

立即下载

摘要：

Deterministicquantumsearchwithadjustableparameters:implementationsandapplicationsGuanzhongLi*andLvzhouLiInstituteofQuantumComputingandComputerTheory,SchoolofComputerScienceandEngineering,SunYat-senUniversity,Guangzhou510006,ChinaFebruary3,2023AbstractGrover'salgorithmprovidesaquadraticspeedupovercl...

展开>> 收起<<

Deterministic quantum search with adjustable parameters implementations and applications Guanzhong Liand Lvzhou Li_2.pdf

共22页,预览5页

还剩页未读，继续阅读

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

Deterministic quantum search with adjustable parameters implementations and applications Guanzhong Liand Lvzhou Li_2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: