Quantumalgorithmsforalgebraicproblems资源-CSDN文库

代数问题的量

Andrew

需积分: 9 8 浏览量 2019-03-12 00:01:52 上传评论 1 收藏 888KB PDF 举报

资源推荐

资源详情

资源评论

arXiv:0812.0380v1 [quant-ph] 2 Dec 2008

Quantum algorithms for algebraic problems

Andrew M. Childs

∗

Department of Combinatorics & Optimization and Institute for Quantum Computing

University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

Wim van Dam

†

Departments of Computer Science and Physics

University of California, Santa Barbara, California 93106, USA

Quantum computers can execute algorithms that dramatically outperform classical computation. As the

best-known example, Shor discovered an efﬁcient quantum algorithm for factoring integers, whereas factoring

appears to be difﬁcult for classical computers. Understanding what other computational problems can be

solved signiﬁcantly faster using quantum algorithms is one of the major challenges in the theory of quantum

computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This

article reviews the current state of quantum algorithms, focusing on algorithms with superpolynomial speedup

over classical computation, and in particular, on problems with an algebraic ﬂavor.

PACS numbers: 03.67.Lx

Contents

I. Introduction

II. Complexity of Quantum Computation 3

A. Quantum data 3

B. Quantum circuits 3

C. Reversible computation 4

D. Quantum complexity theory 5

E. Fault tolerance 5

III. Abelian Quantum Fourier Transform 6

A. Fourier transforms over ﬁnite Abelian groups 6

B. Efﬁcient quantum circuit for the QFT over Z/2

Z 6

C. Phase estimation and the QFT over any ﬁnite Abelian group 7

D. The QFT over a ﬁnite ﬁeld 8

IV. Abelian Hidden Subgroup Problem 8

A. Period ﬁnding over Z/NZ 8

B. Computing discrete logarithms 9

1. Discrete logarithms and cryptography 9

2. Shor’s algorithm for discrete log 9

C. Hidden subgroup problem for ﬁnite Abelian groups 10

D. Period ﬁnding over Z 11

E. Factoring integers 13

F. Breaking elliptic curve cryptography 14

G. Decomposing Abelian and solvable groups 15

H. Counting points on curves 16

V. Quantum Algorithms for Number Fields 19

A. Pell’s equation 19

B. From Pell’s equation to the unit group 19

C. Periodic function for Pell’s equation 20

D. Period ﬁnding over R 20

E. The principal ideal problem and number ﬁeld cryptography 21

F. Computing the unit group of a general number ﬁeld 22

G. The principal ideal problem and the class group 22

VI. Non-Abelian Quantum Fourier Transform 23

A. The Fourier transform over a non-Abelian group 23

B. Efﬁcient quantum circuits 24

∗

amchilds@uwaterloo.ca

†

vandam@cs.ucsb.edu

VII. Non-Abelian Hidden Subgroup Problem 24

A. The problem and its applications 24

B. The standard method 25

C. Weak Fourier sampling 26

D. Strong Fourier sampling 27

E. Multi-register measurements and query complexity 27

F. The Kuperberg sieve 29

G. Pretty good measurement 31

VIII. Hidden Shift Problem 34

A. Abelian Fourier sampling for the dihedral HSP 34

B. Finding hidden shifts in (Z/pZ)

C. Self-reducibility, quantum hiding, and the orbit coset problem 35

D. Shifted Legendre symbol and Gauss sums 36

1. Shifted Legendre symbol problem 36

2. Estimating Gauss sums 37

E. Generalized hidden shift problem 38

IX. Hidden Nonlinear Structures 39

A. The hidden polynomial problem 39

B. Shifted subset problems and exponential sums 40

C. Polynomial reconstruction by Legendre symbol evaluation 41

X. Approximating #P-Complete Problems 41

Acknowledgments 43

A. Number Theory 43

1. Arithmetic modulo N 43

2. Finite ﬁelds and their extensions 43

3. Structure of ﬁnite ﬁelds 44

B. Representation Theory of Finite Groups 44

1. General theory 44

2. Abelian groups 45

3. Dihedral group 45

C. Curves Over Finite Fields 46

1. Afﬁne and projective spaces 46

2. Projective curves 46

3. Properties of curves 46

4. Rational functions on curves 47

References 47

I. INTRODUCTION

In the early 1980s,

Manin (1980) and Feynman (1982) in-

dependently observed that computers built from quantum me-

chanical components would be ideally suited to simulating

quantum mechanics. Whereas brute-force classical simula-

tion of a system of n quantum particles (say, two-level atoms)

requires storing 2

complex amplitudes, and hence exponen-

tially many bits of information, a quantum computer can nat-

urally represent those amplitudes using only n quantum bits.

Thus, it is natural to expect a quantum mechanical computer

to outperform a classical one at quantum simulation.

The perspective of quantum systems as abstract informa-

tion processing devices subsequently led to the identiﬁcation

of concrete tasks, apparently unrelated to quantum mechan-

ics, for which quantum computers have a quantiﬁable advan-

tage.

Deutsch (1985) gave the ﬁrst such example, a black-

box problem that requires two queries to solve on a clas-

sical computer, but that can be solved with only one quan-

tum query. A series of related results (

Bernstein and Vazirani,

1997; Deutsch and Jozsa, 1992) gave increasingly dramatic

separations between classical and quantum query complex-

ity, culminating in an example of

Simon (1997) providing an

exponential separation. Building on this work, Shor (1997)

discovered in 1994 that a quantum computer could efﬁciently

factor integers and calculate discrete logarithms. Shor’s re-

sult drew considerable attention to the concept of quantum in-

formation processing (see

Ekert and Jozsa (1996) for an early

review), and since then, the design and analysis of quantum

algorithms has become a vibrant research area.

Quantum computers achieve speedup over classical compu-

tation by taking advantage of interference between quantum

amplitudes. Of course, interference occurs in classical wave

mechanics as well, but quantum mechanics is distinguished

by the ability to efﬁciently represent a large number of am-

plitudes with only a few quantum bits.

In Shor’s algorithm

and its predecessors, the “exponential interference” leading

to quantum speedup is orchestrated using a unitary operation

called the quantum Fourier transform (QFT), an algebraic op-

eration. In this article, we review the state of the art in quan-

tum algorithms for algebraic problems, which can be viewed

as continuations of the line of work leading from Deutsch to

Shor. Many, though not all, of these algorithms make use of

In principle, quantum systems evolving according to simple interactions

from a simple initial conﬁguration can be described using fewer param-

eters, and classical simulations exploiting this idea have been developed

(see for example

P´erez-Garc´ıa et al. (2007)). But while these ideas are

extremely fruitful for simulating some quantum systems, we do not ex-

pect them to be efﬁcient for any physically reasonable system—in particu-

lar, not for systems capable of performing universal quantum computation.

However, we emphasize that there is no unconditional proof that classical

simulation of quantum systems requires exponential overhead.

A similar situation occurs for the description of n probabilistic bits by

real-valued probabilities. However, probabilities do not interfere; and

contrary to the quantum case, randomized algorithms are not believed to

be dramatically more powerful than deterministic ones (see for example

Impagliazzo and Wigderson (1997)).

the QFT in some capacity.

Before beginning our exploration of quantum algorithms

for algebraic problems, we brieﬂy summarize the develop-

ment of quantum algorithms more generally. It has sometimes

been said that there are really only two quantum algorithms:

Shor’s and Grover’s. We hope that this article will, in some

small way, help to dispel this pernicious myth. While it is dif-

ﬁcult to compete with the impact of Shor’s algorithm (a dra-

matic speedup for a problem profoundly relevant to modern

electronic commerce) or the broad applicability of Grover’s

algorithm (a modest yet surprising speedup for the most basic

of search problems), recent years have seen a steady stream of

new quantum algorithms, both for artiﬁcial problems that shed

light on the power of quantum computation, and for problems

of genuine practical interest.

In 1996,

Grover (1997) gave an algorithm achieving

quadratic speedup

for the unstructured search problem, the

problem of deciding whether a black-box Boolean func-

tion has any input that evaluates to 1. Grover’s algo-

rithm was subsequently generalized to the framework of

amplitude ampliﬁcation and to counting the number of so-

lutions (

Brassard et al., 2002). The unstructured search

problem is extremely basic, and Grover’s algorithm has

found application to a wide variety of related problems

(e.g.,

Ambainis and

Spalek (2006); Brassard et al. (1997);

D¨urr et al. (2004)).

The concept of quantum walk, developed by analogy to the

classical notion of random walk, has proven to be another

broadly useful tool for quantum algorithms. Continuous-

time quantum walk was introduced by

Farhi and Gutmann

(1998), and discrete-time quantum walk was introduced by

Watrous (2001b). The continuous-time formulation has been

used to demonstrate exponential speedup of quantum over

classical computation (

Childs et al., 2003, 2007), though it

remains to be seen whether these ideas can be applied to

a problem of practical interest. However, both continuous-

and discrete-time quantum walk have been applied to achieve

polynomial speedup for a variety of search problems. Follow-

ing related work on spatial search (

Aaronson and Ambainis,

2005; Ambainis et al., 2005; Childs and Goldstone, 2004a,b;

Shenvi et al., 2003), Ambainis (2007) gave an optimal quan-

tum algorithm for the element distinctness problem. This ap-

proach was subsequently generalized (

Magniez et al., 2007;

Szegedy, 2004) and applied to other problems in query com-

plexity, namely triangle ﬁnding (

Magniez et al., 2005), check-

ing matrix multiplication (Buhrman and

Spalek, 2006), and

testing group commutativity (

Magniez and Nayak, 2007). Re-

cently, quantum walk has also been applied to give optimal

quantum algorithms for evaluating balanced binary game trees

(

Farhi et al., 2007) and, more generally, Boolean formulas

(

Ambainis et al., 2007; Reichardt and

Spalek, 2008).

Prior to Grover’s result it was already shown by Bennett et al. (1997) that

a quadratic speedup for the unstructured search problem is optimal. More

generally, for any total Boolean function, there can be be at most a polyno-

mial separation (in general, at most degree 6) between classical and quan-

tum query complexity (

Beals et al., 2001).

A related technique for quantum algorithms is the concept

of adiabatic evolution. The quantum adiabatic theorem guar-

antees that a quantum system in its ground state will remain

close to its ground state as the Hamiltonian is changed, pro-

vided the change is sufﬁciently slow, depending on spectral

properties of the Hamiltonian (see for example

Born and Fock

(1928); Jansen et al. (2007)). Farhi et al. (2000) proposed us-

ing adiabatic evolution as an approach to optimization prob-

lems. Unfortunately, analyzing this approach is challeng-

ing. While it is possible to construct speciﬁc cost functions

for which speciﬁc formulations of adiabatic optimization fail

(

van Dam et al., 2001; van Dam and Vazirani, 2003; Fisher,

1992; Reichardt, 2004), the performance in general remains

poorly understood. Going beyond the setting of optimization

problems, note that adiabatic evolution can simulate a univer-

sal quantum computer (

Aharonov et al., 2007b).

Finally, returning to the original motivation for quan-

tum computation, Manin and Feynman’s vision of quan-

tum computers as quantum simulators has been considerably

developed (e.g.,

Aspuru-Guzik et al. (2005); Lloyd (1996);

Wiesner (1996); Zalka (1998)). However, it has proven difﬁ-

cult to identify a concrete computational task involving quan-

tum simulation for which the speedup over classical comput-

ers can be understood precisely. While it is widely expected

that quantum simulation will be one of the major applications

of quantum computers, much work remains to be done.

The main body of this article is organized as follows. In

Section

II, we give a brief introduction to the model of quan-

tum computation and the complexity of quantum algorithms.

In Section

III, we introduce the Abelian quantum Fourier

transform, and in Section

IV, we show how this transform

can be applied to solve the Abelian hidden subgroup problem,

with various applications. In Section

V, we describe quantum

algorithms for problems involving number ﬁelds, including

the efﬁcient quantum algorithm for solving Pell’s equation. In

Section

VI, we introduce the non-Abelian version of the quan-

tum Fourier transform, and in Section

VII we discuss the sta-

tus of the non-Abelian version of the hidden subgroup prob-

lem. In Sections

VIII and IX, we describe two approaches to

going beyond the hidden subgroup framework, namely hid-

den shift problems and hidden nonlinear structure problems,

respectively. Finally, in Section

X, we brieﬂy discuss quan-

tum algorithms for approximating the Jones polynomial and

other #P-complete problems.

II. COMPLEXITY OF QUANTUM COMPUTATION

In this section we give a brief introduction to quantum com-

puters, with particular emphasis on characterizing computa-

tional efﬁciency. For more detailed background, the reader is

encouraged to consult

Kaye et al. (2007); Kitaev et al. (2002);

Nielsen and Chuang (2000); Preskill (1998a).

A. Quantum data

A quantum computer is a device for performing calcula-

tions using a quantum mechanical representation of informa-

tion. Data are stored using quantum bits, or qubits, the states

of which can be represented by ℓ

-normalized vectors in a

complex vector space. For example, we can write the state

of n qubits as

|ψi =

∑

x∈{0,1}

|xi (1)

where the a

∈ C satisfy

∑

x∈{0,1}

n |a

= 1. We refer to the

basis of states |xi as the computational basis.

Although we can always suppose that our data is repre-

sented using qubits, it is often useful to think of quantum

states as storing data more abstractly. For example, given a

group G, we write |gi for a computational basis state corre-

sponding to the group element g ∈ G, and

|φi =

∑

g∈G

|gi (2)

(where b

∈ C with

∑

g∈G

= 1) for an arbitrary superpo-

sition over the group. We often implicitly assume that there is

some canonical way of concisely representing group elements

using bit strings; it is usually unnecessary to make this repre-

sentation explicit. We use the convention that for any ﬁnite set

S, the state |Si denotes the normalized uniform superposition

of its elements, i.e.,

|Si :=

|S|

∑

s∈S

|si. (3)

If a quantum computer stores the state |ψi in one register

and the state |φi in another, the overall state is given by the

tensor product of those two states. This may variously be de-

noted |ψi⊗|φi, |ψi|φi, or |ψ,φi.

It can be useful to consider statistical mixtures of pure

quantum states, represented by density matrices. We refer the

reader to the references above for further details.

B. Quantum circuits

The allowed operations on pure quantum states are those

that map normalized states to normalized states, namely uni-

tary operators U, satisfying UU

†

= U

†

U = 1. When viewed

as an N ×N matrix, the rows (and columns) of U form an

orthonormal basis of the space C

To have a sensible notion of efﬁcient computation, we re-

quire that the unitary operators appearing in a quantum com-

putation are realized by quantum circuits (

Deutsch, 1989;

Yao, 1993). We are given a set of gates, each of which acts

on one or two qubits at a time, meaning that it is a tensor

product of a nontrivial one- or two-qubit operator with the

identity operator on the remaining qubits. A quantum compu-

tation begins in the |0.. .0i state, applies a sequence of one-

and two-qubit gates chosen from the set of allowed gates, and

ﬁnally reports an outcome obtained by measuring in the com-

putational basis. A circuit is called efﬁcient if it contains a

number of gates that is polynomial in the number of qubits

the circuit acts on.

In principle, any unitary operator on n qubits can be imple-

mented using only 1- and 2-qubit gates (DiVincenzo, 1995).

Thus we say that the set of all 1- and 2-qubit gates is (exactly)

universal. Of course, some unitary operators take many more

1- and 2-qubit gates to realize than others, and indeed, a sim-

ple counting argument shows that most unitary operators on n

qubits can only be realized using an exponentially large circuit

(

Knill, 1995).

In general, we are content with circuits that give good ap-

proximations of our desired unitary transformations. We say

that a circuit with gates U

,. .. ,U

approximates U with

precision ε if kU −U

···U

k ≤ ε, where k·k denotes the

operator norm, i.e., the largest singular value. We call a set of

elementary gates universal if any unitary operator on a ﬁxed

number of qubits can be approximated to precision ε using

poly(log

) elementary gates. It turns out that there are ﬁnite

sets of gates that are universal (

Boykin et al., 2000): for ex-

ample, the set {H,T, Λ(X)} with

H :=

√



1 1

1 −1



T :=



iπ/8

0 e

−iπ/8



(4)

Λ(X) :=







1 0 0 0

0 1 0 0

0 0 0 1

0 0 1 0







. (5)

There are situations in which a set of gates is effectively

universal, even though it cannot actually approximate any

unitary operator on n qubits. For example, the gate set

{H, T

,Λ(X),Λ

(X)}, where Λ

(X) denotes the Toffoli gate

(Λ

(X)|xyzi = |xyzi for xy ∈ {00,01,10}, and Λ

(X)|11zi =

|11¯zi) is universal (

Kitaev, 1997), but only if we allow the

use of ancilla qubits (qubits that start and end in the |0i

state). Similarly, the gate set {H,Λ

(X)} is universal in the

sense that, with ancillas, it can approximate any orthogo-

nal transformation (

Aharonov, 2003; Shi, 2003). It clearly

cannot approximate complex unitary matrices, since the en-

tries of H and Λ

(X) are real; but the effect of arbitrary

unitary transformations can be simulated using orthogonal

ones by simulating the real and imaginary parts separately

(

Bernstein and Vazirani, 1993; Rudolph and Grover, 2002).

One might wonder whether some universalgate sets are bet-

ter than others. It turns out that the answer is essentially no:

a unitary operator that can be realized efﬁciently with one set

of 1- and 2-qubit gates can also be realized efﬁciently with

another such set. This is a consequence of the Solovay-Kitaev

theorem (

Harrow et al., 2002; Kitaev, 1997; Solovay, 2000):

Theorem 1. Fix two gate sets that allow universal quantum

computation and that are closed under taking inverses. Then

any t-gate circuit using the ﬁrst gate set can be implemented

with error at most ε using a circuit of t ·poly(log(t/ε)) gates

from the second gate set. Furthermore, there is an efﬁcient

classical algorithm for ﬁnding this circuit.

In particular, this means we can view a simple ﬁnite gate

set, such as {H, T, Λ(X)}, as equivalent to an inﬁnite gate

set, such as the set of all two-qubit gates. A ﬁnite gate set

is needed both for fault tolerance (Section

II.E) and for the

concept of uniformly generated circuits (Footnote

4).

Note that to implement unitary operators exactly, the no-

tion of efﬁciency might depend on the allowed gates (see for

example

Mosca and Zalka (2004)), so we usually restrict our

attention to quantum computation with bounded error.

In principle, one can construct quantum circuits adaptively,

basing the choices of gates on the outcomes of intermedi-

ate measurements. We may also discard quantum data in

the course of a circuit. In general, the possible operations

on mixed quantum states correspond to completely positive,

trace preserving maps on density matrices. Again, we refer

the reader to the aforementioned references for more details.

C. Reversible computation

Unitary matrices are invertible: in particular, U

−1

= U

†

Thus any unitary transformation is a reversible operation.

This may seem at odds with how we often deﬁne classical

circuits, using irreversible gates such as AND and OR. But

any classical computation can be made reversible by replac-

ing each irreversible gate x 7→ g(x) by the reversible gate

(x,y) 7→ (x,y⊕g(x)), where ⊕ denotes bitwise addition mod-

ulo 2. Applying this gate to the input (x,0) produces (x, g(x)).

By storing all intermediate steps of the computation, we make

it reversible (Bennett, 1973).

On a quantum computer, storing all intermediate computa-

tional steps could present a problem, since two identical re-

sults obtained via distinct computational histories would not

be able to interfere. However, there is an easy way to remove

the accumulated information. After performing the classical

computation with reversible gates, we simply copy the answer

into an ancilla register, and then perform the computation in

reverse. Thus we can implement the map (x,y) 7→(x,y⊕ f(x))

even when f is a complicated circuit consisting of many gates.

Using this trick, any computation that can be performed ef-

ﬁciently on a classical computer can be performed efﬁciently

on a quantum computer, even on a superposition of computa-

tional basis states. In other words, if we can efﬁciently im-

plement the map x 7→ f(x) on a classical computer, we can

efﬁciently perform the transformation

∑

|x,yi 7→

∑

|x,y ⊕ f (x)i (6)

on a quantum computer. Note that this does not necessarily

mean we can efﬁciently perform the transformation

∑

|xi 7→

∑

|f(x)i, (7)

even if the function f is bijective.

D. Quantum complexity theory

We say that an algorithm for a problem is efﬁcient if the

circuit describing it uses a number of gates that is polynomial

in the input size, the number of bits needed to write down the

input.

For example, if the input is an integer modulo N, the

input size is ⌈log

N⌉.

With a quantum computer, as with a randomized (or noisy)

classical computer, the ﬁnal result of a computation may not

be correct with certainty. Instead, we are typically content

with an algorithm that can produce the correct answer with

high enough probability. To solve a decision problem, it suf-

ﬁces to give an algorithm with success probability bounded

above 1/2 (say, at least 2/3), since we can repeat the compu-

tation many times and take a majority vote to make the proba-

bility of outputting an incorrect answer arbitrarily small. Sim-

ilarly, if we can check whether a given solution is correct, it

sufﬁces to output the correct answer with probability Ω(1).

It is common practice to characterize the difﬁculty of com-

putational problems using complexity classes (see for example

Papadimitriou (1994)). Typically, these classes contain deci-

sion problems, problems with a ‘yes’ or ‘no’ answer. (Such

a problem is conventionally formulated as deciding whether

a string over some ﬁnite alphabet is in a given language; for-

mally, a complexity class is a set of languages.) For example,

the problems that can be decided in polynomial time on a de-

terministic classical computer belong to the class P; on a prob-

abilistic classical computer with error at most 1/3, to the class

BPP; and on a quantum computer with error at most 1/3, to

the class BQP. Clearly, P ⊆BPP ⊆BQP. The central problem

of quantum algorithms can be viewed as trying to understand

what problems are in BQP, but not in P (or BPP).

Whereas the classes P, BPP, and BQP all attempt to char-

acterize modes of computation that could be carried out in

practice, computational complexity theory is also concerned

with more abstract classes that characterize other aspects of

computation. For example, the class NP corresponds to those

decision problems for which a ‘yes’ answer can be veriﬁed

in polynomial time on a classical computer, given a succinct

proof. It is widely believed that P 6= NP, and indeed, that

NP 6⊆ BQP (though it is also plausible that BQP 6⊆ NP), but

proving this appears to be an extremely challenging prob-

Strictly speaking, we would like the circuits for solving instances of a prob-

lem of different sizes to be related to one another in some simple way.

Given the ability to choose an arbitrary circuit for each input size, we could

even have circuits computing uncomputable functions (i.e., functions that a

Turing machine could not compute). Thus we require our circuits to be uni-

formly generated: say, that there exists a ﬁxed (classical) Turing machine

that, given a tape containing the symbol ‘1’ n times, outputs a description

of the nth circuit in time poly(n).

In this article, we use standard big-O notation, where f = O(g) if there exist

positive constants c,y such that |f(x)| ≤ c|g(x)| for all x ≥ y; f = Ω(g) if

g = O( f); and f = Θ(g) if both f = O(g) and f = Ω(g). The expression

Ω(1) thus represents a function lower bounded by an unspeciﬁed positive

constant. We write f = o(g) to denote that lim

x→∞

f(x)/g(x) = 0. To

convey that a function f is bounded from above by a polynomial in the

function g, we write f = poly(g), which could also be written as f = g

O(1)

lem (see for example the excellent survey of quantum com-

plexity by

Watrous (2009)). Indeed, it seems almost as difﬁ-

cult just to prove P 6= PSPACE, where PSPACE denotes the

class of problems that can be decided by a deterministic clas-

sical computer running in polynomial space. Since BQP ⊆

PSPACE (

Bernstein and Vazirani, 1997) (i.e., any computa-

tion that can be performed on a quantum computer in poly-

nomial time can be performed on a classical computer with

polynomial memory—indeed, even stronger such results are

known (

Adleman et al., 1997; Bernstein and Vazirani, 1997;

Fortnow and Rogers, 1998)), we expect it will be hard to

prove P 6= BQP. Instead, we try to ﬁnd efﬁcient quantum

algorithms for problems that appear to be hard for classical

computers.

While most complexity classes contain decision problems,

some classes describe the complexity of computing non-

Boolean functions. For example, the class #P characterizes

the complexity of counting the number of ‘yes’ solutions to a

problem in NP.

Alternatively, instead of considering natural computational

problems (in which the input is a string), we sometimes work

in the setting of query complexity. Here the input is a black-

box transformation (or oracle)—which in the quantum setting

is given as a unitary transformation as in Eq. (

6)—and our goal

is to discover some property of the transformation by querying

it as few times as possible. For example, in Simon’s problem

(

Simon, 1997), we are given a black box for a transformation

f : {0, 1}

→ S satisfying f(x) = f(y) iff y ∈ {x, x ⊕t} for

some unknown t ∈ {0,1}

, and the goal is to learn t.

The query model facilitates proving lower bounds: it is of-

ten tractable to establish that many queries must be used to

solve a given black-box problem, whereas it is generally hard

to show that many gates are required to compute some ex-

plicit function. Indeed, we will encounter numerous exam-

ples of black-box problems that can be solved in polynomial

time on a quantum computer, but that provably require expo-

nentially many queries on a randomized classical computer.

Of course, if we ﬁnd an efﬁcient algorithm for a problem in

query complexity, then if we are provided with an explicit, ef-

ﬁcient circuit realizing the black-box transformation, we will

have an efﬁcient algorithm for a natural computational prob-

lem. We stress, however, that lower bounds in the query model

no longer apply when the black box is thus replaced by a trans-

parent one. For example, Shor’s factoring algorithm (Sec-

tion

IV.E) proceeds by solving a problem in query complexity

which is provably hard for classical computers. Nevertheless,

it is an open question whether factoring is classically hard,

since there might be a fast classical algorithm that does not

work by solving the query problem.

E. Fault tolerance

With any real computer, operations cannot be done per-

fectly. Quantum gates and measurements may be performed

imprecisely, and errors may happen even to stored data that

is not being manipulated. Fortunately, there are protocols for

dealing with faults that occur during the execution of a quan-

剩余51页未读，继续阅读

评论收藏

内容反馈

Dai&Wenjing

粉丝: 0
资源: 5

Quantum algorithms for algebraic problems

Quantum Algorithms for Optimization and Polynomial Systems

Practical Quantum Computing for Developers

Quantum Algorithms via Linear Algebra

Quantum Mechanics for Scientists and Engineers

Quantum Computing for Computer Architects, 2nd Edition, MC, Mar 2011.pdf

Quantum Computation and Quantum Information

Quantum walks_a comprehensive review

Quantum Programming for Embedded Systems英文PDF和光盘资料_01

Quantum Computing for the Quantum Curious 奇妙的量子计算

Learning the quantum algorithm for state overlap.pdf

GTM267 Quantum Theory for Mathematicians, Brian C. Hall, Springer 2013.pdf

1511.02306 Quantum algorithm for systems of linear equations.pdf

quantum optics toolbox for MATLAB.rar_matlab_matlab optics_quant

2018 The-Theory-of-Quantum-Information.pdf

Introduction to quantum machine learning for engineer

BURAI 1.2 – a GUI for Quantum Espresso

Quantum Espresso 6.4.1 for linux

A Introduction to Quantum Computing for

Steady state quantum discord for circularly accelerated atoms

Quantum_quantumcomputing_quantum_pdfword_

A Quantum Optics Toolbox for Matlab 5.pdf

Quantum Programming for Embedded Systems英文PDF和光盘资料_说明

Quantum Programming for Embedded Systems英文PDF和光盘资料_02

Quantum Programming for Embedded Systems英文PDF和光盘资料_03

Quantum Programming for Embedded Systems英文PDF和光盘资料_04

最新资源