Function Maximization with Dynamic Quantum Search

Charles Moussa; Henri Calandra; Travis S. Humble

doi:10.1007/978-3-030-14082-3_8

Function Maximization with Dynamic Quantum Search

Charles Moussa, Henri Calandra, Travis S. Humble

Quantum Science Center

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

Finding the maximum value of a function in a dynamic model plays an important role in many application settings, including discrete optimization in the presence of hard constraints. We present an iterative quantum algorithm for finding the maximum value of a function in which prior search results update the acceptable response. Our approach is based on quantum search and utilizes a dynamic oracle function to mark items in a specified input set. As a realization of function optimization, we verify the correctness of the algorithm using numerical simulations of quantum circuits for the Knapsack problem. Our simulations make use of an explicit oracle function based on arithmetic operations and a comparator subroutine, and we verify these implementations using numerical simulations up to 30 qubits.

Original language	English
Title of host publication	Quantum Technology and Optimization Problems - 1st International Workshop, QTOP 2019, Proceedings
Editors	Sebastian Feld, Claudia Linnhoff-Popien
Publisher	Springer Verlag
Pages	86-95
Number of pages	10
ISBN (Print)	9783030140816
DOIs	https://doi.org/10.1007/978-3-030-14082-3_8
State	Published - 2019
Event	1st International Workshop on Quantum Technology and Optimization Problems, QTOP 2019 was held in conjunction with the International Conference on Networked Systems, NetSys 2019 - Munich, Germany Duration: Mar 18 2019 → Mar 18 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11413 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	1st International Workshop on Quantum Technology and Optimization Problems, QTOP 2019 was held in conjunction with the International Conference on Networked Systems, NetSys 2019
Country/Territory	Germany
City	Munich
Period	03/18/19 → 03/18/19

Funding

T. S. Humble—This manuscript has been authored by UT-Battelle, LLC, under Contract No. DE-AC0500OR22725 with the U.S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for the United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan.

Keywords

Maximization
Quantum optimization
Quantum search

Access to Document

10.1007/978-3-030-14082-3_8

Cite this

Moussa, C., Calandra, H., & Humble, T. S. (2019). Function Maximization with Dynamic Quantum Search. In S. Feld, & C. Linnhoff-Popien (Eds.), Quantum Technology and Optimization Problems - 1st International Workshop, QTOP 2019, Proceedings (pp. 86-95). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11413 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-14082-3_8

Moussa, Charles ; Calandra, Henri ; Humble, Travis S. / Function Maximization with Dynamic Quantum Search. Quantum Technology and Optimization Problems - 1st International Workshop, QTOP 2019, Proceedings. editor / Sebastian Feld ; Claudia Linnhoff-Popien. Springer Verlag, 2019. pp. 86-95 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ba2f3e5e7870491cbab874302877416c,

title = "Function Maximization with Dynamic Quantum Search",

abstract = "Finding the maximum value of a function in a dynamic model plays an important role in many application settings, including discrete optimization in the presence of hard constraints. We present an iterative quantum algorithm for finding the maximum value of a function in which prior search results update the acceptable response. Our approach is based on quantum search and utilizes a dynamic oracle function to mark items in a specified input set. As a realization of function optimization, we verify the correctness of the algorithm using numerical simulations of quantum circuits for the Knapsack problem. Our simulations make use of an explicit oracle function based on arithmetic operations and a comparator subroutine, and we verify these implementations using numerical simulations up to 30 qubits.",

keywords = "Maximization, Quantum optimization, Quantum search",

author = "Charles Moussa and Henri Calandra and Humble, {Travis S.}",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 1st International Workshop on Quantum Technology and Optimization Problems, QTOP 2019 was held in conjunction with the International Conference on Networked Systems, NetSys 2019 ; Conference date: 18-03-2019 Through 18-03-2019",

year = "2019",

doi = "10.1007/978-3-030-14082-3_8",

language = "English",

isbn = "9783030140816",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "86--95",

editor = "Sebastian Feld and Claudia Linnhoff-Popien",

booktitle = "Quantum Technology and Optimization Problems - 1st International Workshop, QTOP 2019, Proceedings",

}

Moussa, C, Calandra, H & Humble, TS 2019, Function Maximization with Dynamic Quantum Search. in S Feld & C Linnhoff-Popien (eds), Quantum Technology and Optimization Problems - 1st International Workshop, QTOP 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11413 LNCS, Springer Verlag, pp. 86-95, 1st International Workshop on Quantum Technology and Optimization Problems, QTOP 2019 was held in conjunction with the International Conference on Networked Systems, NetSys 2019, Munich, Germany, 03/18/19. https://doi.org/10.1007/978-3-030-14082-3_8

Function Maximization with Dynamic Quantum Search. / Moussa, Charles; Calandra, Henri; Humble, Travis S.
Quantum Technology and Optimization Problems - 1st International Workshop, QTOP 2019, Proceedings. ed. / Sebastian Feld; Claudia Linnhoff-Popien. Springer Verlag, 2019. p. 86-95 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11413 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Function Maximization with Dynamic Quantum Search

AU - Moussa, Charles

AU - Calandra, Henri

AU - Humble, Travis S.

PY - 2019

Y1 - 2019

N2 - Finding the maximum value of a function in a dynamic model plays an important role in many application settings, including discrete optimization in the presence of hard constraints. We present an iterative quantum algorithm for finding the maximum value of a function in which prior search results update the acceptable response. Our approach is based on quantum search and utilizes a dynamic oracle function to mark items in a specified input set. As a realization of function optimization, we verify the correctness of the algorithm using numerical simulations of quantum circuits for the Knapsack problem. Our simulations make use of an explicit oracle function based on arithmetic operations and a comparator subroutine, and we verify these implementations using numerical simulations up to 30 qubits.

AB - Finding the maximum value of a function in a dynamic model plays an important role in many application settings, including discrete optimization in the presence of hard constraints. We present an iterative quantum algorithm for finding the maximum value of a function in which prior search results update the acceptable response. Our approach is based on quantum search and utilizes a dynamic oracle function to mark items in a specified input set. As a realization of function optimization, we verify the correctness of the algorithm using numerical simulations of quantum circuits for the Knapsack problem. Our simulations make use of an explicit oracle function based on arithmetic operations and a comparator subroutine, and we verify these implementations using numerical simulations up to 30 qubits.

KW - Maximization

KW - Quantum optimization

KW - Quantum search

UR - http://www.scopus.com/inward/record.url?scp=85064049775&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-14082-3_8

DO - 10.1007/978-3-030-14082-3_8

M3 - Conference contribution

AN - SCOPUS:85064049775

SN - 9783030140816

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 86

EP - 95

BT - Quantum Technology and Optimization Problems - 1st International Workshop, QTOP 2019, Proceedings

A2 - Feld, Sebastian

A2 - Linnhoff-Popien, Claudia

PB - Springer Verlag

T2 - 1st International Workshop on Quantum Technology and Optimization Problems, QTOP 2019 was held in conjunction with the International Conference on Networked Systems, NetSys 2019

Y2 - 18 March 2019 through 18 March 2019

ER -

Moussa C, Calandra H, Humble TS. Function Maximization with Dynamic Quantum Search. In Feld S, Linnhoff-Popien C, editors, Quantum Technology and Optimization Problems - 1st International Workshop, QTOP 2019, Proceedings. Springer Verlag. 2019. p. 86-95. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-14082-3_8

Function Maximization with Dynamic Quantum Search

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this