Phase Transitions for Quantum Search Algorithms

Hogg, Tad

doi:10.1093/oso/9780195177374.003.0019

Chapter

10 Phase Transitions for Quantum Search Algorithms

Get access

https://doi.org/10.1093/oso/9780195177374.003.0019

Pages

223–247

Published:

December 2005

Abstract

Phase transitions have long been studied empirically in various combinatorial searches and theoretically in simplified models [91, 264, 301, 490]. The analogy with statistical physics [397], explored throughout this volume, shows how the many local choices made during search relate to global properties such as the resulting search cost. These studies have led to a better understanding of typical search behaviors [514] and improved search methods [195, 247, 261, 432, 433]. Among the current research questions in this field are the range of algorithms exhibiting the transition behavior and the algorithm-independent problem properties associated with the difficult instances concentrated near the transition. Towards this end, the present chapter examines quantum computer [123, 126, 158, 486] algorithms for nondeterministic polynomial (NP) combinatorial search problems [191]. As with many conventional methods, they exhibit the easy-hard-easy pattern of computational cost as the degree of constraint in the problems varies. We describe how properties of the search space affect the algorithms and identify an additional structural property, the energy gap, motivated by one quantum algorithm but applicable to a variety of techniques, both quantum and classical. Thus, the study of quantum search algorithms not only extends the range of algorithms exhibiting phase transitions, but also helps identify underlying structural properties. Specifically, the next two sections describe a class of hard search problems and the form of quantum search algorithms proposed to date. The remainder of the chapter presents algorithm behaviors, relevant problem structure, arid an approximate asymptotic analysis of their cost scaling. The final section discusses various open issues in designing and evaluating quantum algorithms, and relating their behavior to problem structure. The k-satisfiability (k -SAT) problem, as discussed earlier in this volume, consists of n Boolean variables and m clauses. A clause is a logical OR of k variables, each of which may be negated. A solution is an assignment, that is, a value for each variable, TRUE or FALSE, satisfying all the clauses. An assignment is said to conflict with any clause it does not satisfy.

You do not currently have access to this chapter.

Sign in with email/username & password
Get email alerts
Save searches
Purchase content
Activate your purchase/trial code
Add your ORCID iD

Get help with access

Institutional access

Access to content on Oxford Academic is often provided through institutional subscriptions and purchases. If you are a member of an institution with an active account, you may be able to access content in one of the following ways:

IP based access

Typically, access is provided across an institutional network to a range of IP addresses. This authentication occurs automatically, and it is not possible to sign out of an IP authenticated account.

Sign in through your institution

Choose this option to get remote access when outside your institution. Shibboleth/Open Athens technology is used to provide single sign-on between your institutionâ€™s website and Oxford Academic.

Click Sign in through your institution.
Select your institution from the list provided, which will take you to your institution's website to sign in.
When on the institution site, please use the credentials provided by your institution. Do not use an Oxford Academic personal account.
Following successful sign in, you will be returned to Oxford Academic.

If your institution is not listed or you cannot sign in to your institutionâ€™s website, please contact your librarian or administrator.

Sign in with a library card

Enter your library card number to sign in. If you cannot sign in, please contact your librarian.

Society Members

Society member access to a journal is achieved in one of the following ways:

Sign in through society site

Many societies offer single sign-on between the society website and Oxford Academic. If you see â€˜Sign in through society siteâ€™ in the sign in pane within a journal:

Click Sign in through society site.
When on the society site, please use the credentials provided by that society. Do not use an Oxford Academic personal account.
Following successful sign in, you will be returned to Oxford Academic.

If you do not have a society account or have forgotten your username or password, please contact your society.

Sign in using a personal account

Some societies use Oxford Academic personal accounts to provide access to their members. See below.

Personal account

A personal account can be used to get email alerts, save searches, purchase content, and activate subscriptions.

Some societies use Oxford Academic personal accounts to provide access to their members.

Viewing your signed in accounts

Click the account icon in the top right to:

View your signed in personal account and access account management features.
View the institutional accounts that are providing access.

Signed in but can't access content

Oxford Academic is home to a wide variety of products. The institutional subscription may not cover the content that you are trying to access. If you believe you should have access to that content, please contact your librarian.

Institutional account management

For librarians and administrators, your personal account also provides access to institutional account management. Here you will find options to view and activate subscriptions, manage institutional settings and access options, access usage statistics, and more.

Metrics

Total Views 8

5 Pageviews

3 PDF Downloads

Since 10/1/2022

Month:	Total Views:
October 2022	1
June 2024	2
July 2024	1
November 2024	2
January 2025	2

Contents

10 Phase Transitions for Quantum Search Algorithms

Abstract

Email alerts

Contents

10 Phase Transitions for Quantum Search Algorithms

Abstract

Sign in

Personal account

Institutional access

Institutional account management

Get help with access

Institutional access

IP based access

Sign in through your institution

Sign in with a library card

Society Members

Sign in through society site

Sign in using a personal account

Personal account

Viewing your signed in accounts

Signed in but can't access content

Institutional account management

Purchase

Email alerts

This Feature Is Available To Subscribers Only