Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer_2

2025-05-06 0 0 175.28KB 11 页 10玖币

侵权投诉

arXiv:2210.04664v2 [quant-ph] 12 Oct 2022

Depth-First Grover Search Algorithm

on Hybrid Quantum-Classical Computer

Haoxiang Guo

yurodidon@gmail.com

Abstract

We demonstrated the detailed construction of the hybrid quantum-classical computer.

Based on this architecture, the useful concept of amplitude interception is illustrated. It is

then embedded into a combination of Depth-First Search and Grover’s algorithm to gen-

erate a novel approach, the Depth-First Grover Search(DFGS), to handle multi-solution

searching problems on unstructured databases with an unknown number of solutions. Our

new algorithm attains an average complexity of O(m√N) which performs as eﬃcient as a

normal Grover Search, and a O(√pN ) complexity with a manually determined constant p

for the case with all elements are solutions, where a normal Grover Search will degenerate

to O(N√N). The DFGS algorithm is more robust and stable in comparison.

Keywords— Quantum Computation, Hybrid Quantum-Classical Computer, Grover’s Algo-

rithm, Unstructured Database Search

1 Introduction

Since the concept of Quantum Computing was proposed[Ben80; Fey85], bunches of quantum

algorithms were designed to achieve quantum supremacy[Pre12]. And these algorithms can be sep-

arated into two large groups: (1) Algorithms based on Quantum Fourier Transformation[Cop02;

Sho94; Sho97] and (2) Algorithms based on oracles[DJ92; BV97; Gro96], in which Grover’s al-

gorithm is able to solve the single-solution unstructured searching problems with a complexity of

O(√N), and was demonstrated to be asymptotic optimal in [Ben+97].

In recent years, a new concept of Hybrid Quantum-Classical(HQC) Computation was

presented[Llo00] and received rising degrees of attention, the concept of HQC is applicated to

several areas in computer science[End+21; Ott+17; Liu+21; Ber+18]. By attaching quantum

components with a classical computer, two parts complement each other, leading HQC to have

both merits of them, e.g., quantum parallelism[NC10], data storing, and eﬃcient arithmetic op-

erations.

Whereas a few articles talk about the detailed structure of HQC, in this paper, we devoted

Section 2 to investigating the conﬁguration of HQC. Furthermore, we confronted the issue of

the ineﬃciency of Grover’s algorithm when applying it to multi-solution search problems (which

will encounter repetitions and worsen up to O(N√N)), and proposed the concept of amplitude

interception and a novel robust algorithm, the Depth-ﬁrst Grover Search based on an HQC

computer in Section 3.

2 Hybrid Quantum-Classical Structure

We aim to design an architecture for HQC with two basic functions:

•The ability to operate quantum parts and classical parts individually.

•The ability to intercommunicate between the quantum part and the classical part.

Both of these functions can be implemented by two components: INITIALIZER and ENCODER.

INITIALIZER component initializes auxiliary qubits for follow-up quantum computing, e.g.,

Haoxiang Guo 2022 Page i

for handling searching problems, it is usually composed with HX gates to get |−i for phase

kickback[Cle+98]. Besides the INITIALIZER, the ENCODER component enables the information

transformation from classical to quantum parts. An example is shown in Figure 1, which directly

copies the digits to qubits.

...

|0iX|q1i

|0iX|qni

Figure 1: An example of ENCODER, composed with ncontrol-not gate

The bridge from the classical part to the quantum part is also proven to have various forms.

In [Suc+18], the quantum part is considered to be arranged in the cloud and intercommunicated

with Internet technology. Recently, IBM constructed 127-qubits quantum computers with remote

accessibility[IBM21], which implies that future quantum computing will have a trend of online-

oﬄine separation. The general architecture of HQC is demonstrated in Figure 2.

Classical Algorithm

Auxiliary Qubits INITIALIZER

Quantum Circuit

Working Qubits ENCODER

Classical Part

Figure 2: The detailed structure of the hybrid quantum-classical computer. In many cases, the auxiliary

qubits are not necessary to be measured.

A crucial feature of this architecture is it allows the implementation of discrete loops[Bli94],

we refer to discrete since we always destroy superpositions after each measurement. Since an

amount of information is inevitably lost during the measurements, so there exists an irremovable

gap between the conditional loops we commonly regard and the discrete loops we have. Or in

other words, we are still unable to implement conditional loops upon this architecture.

In HQC, classical parts can either work as the main parts for performing algorithms or

auxiliary parts for data storing and updating. A sort of classical algorithm can be improved by

replacing some steps(e.g., extreme searching[DH96; AK99; KOW+08]) with quantum algorithms

to obtain better performance[Hei03; AS05]. Furthermore, some other authors proposed variational

hybrid quantum-classical algorithms[McC+16; Ple+22] by regarding classical computers as an

auxiliary part. As well as in [BSS16] the authors discovered a portion of qubits required in

quantum algorithms could be separated and replaced by classical bits with the same eﬃciency

but save quantum resources.

Haoxiang Guo 2022 Page ii

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

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

10 玖币 0人已下载

立即下载

摘要：

arXiv:2210.04664v2[quant-ph]12Oct2022Depth-FirstGroverSearchAlgorithmonHybridQuantum-ClassicalComputerHaoxiangGuoyurodidon@gmail.comAbstractWedemonstratedthedetailedconstructionofthehybridquantum-classicalcomputer.Basedonthisarchitecture,theusefulconceptofamplitudeinterceptionisillustrated.Itisthene...

展开>> 收起<<

Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer_2.pdf

共11页,预览3页

还剩页未读，继续阅读

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

Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer_2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: