Quantum-Enhanced Generalized Pattern Search Optimization
While the development of quantum computers promises a myriad of advantages over their classical counterparts, care must be taken when designing algorithms that substitute a classical technique with a potentially advantageous quantum method. The probabilistic nature of many quantum algorithms may res...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-09-01
|
| Series: | Quantum Reports |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2624-960X/6/4/34 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850084824963874816 |
|---|---|
| author | Colton Mikes David Huckleberry Gutman Victoria E. Howle |
| author_facet | Colton Mikes David Huckleberry Gutman Victoria E. Howle |
| author_sort | Colton Mikes |
| collection | DOAJ |
| description | While the development of quantum computers promises a myriad of advantages over their classical counterparts, care must be taken when designing algorithms that substitute a classical technique with a potentially advantageous quantum method. The probabilistic nature of many quantum algorithms may result in new behavior that could negatively impact the performance of the larger algorithm. The purpose of this work is to preserve the advantages of applying quantum search methods for generalized pattern search algorithms (GPSs) without violating the convergence criteria. It is well known that quantum search methods are able to reduce the expected number of oracle calls needed for finding the solution to a search problem from <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>N</mi><mo>)</mo></mrow></semantics></math></inline-formula> to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><msqrt><mi>N</mi></msqrt><mo>)</mo></mrow></semantics></math></inline-formula> However, the number of oracle calls needed to determine that no solution exists with certainty is exceedingly high and potentially infinite. In the case of GPS, this is a significant problem since overlooking a solution during an iteration will violate a needed assumption for convergence. Here, we overcome this problem by introducing the quantum improved point search (QIPS), a classical–quantum hybrid variant of the quantum search algorithm QSearch. QIPS retains the <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><msqrt><mi>N</mi></msqrt><mo>)</mo></mrow></semantics></math></inline-formula> oracle query complexity of QSearch when a solution exists. However, it is able to determine when no solution exists, with certainty, using only <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>N</mi><mo>)</mo></mrow></semantics></math></inline-formula> oracle calls. |
| format | Article |
| id | doaj-art-cfd9b1b45e224f669f555409d310fef7 |
| institution | DOAJ |
| issn | 2624-960X |
| language | English |
| publishDate | 2024-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Quantum Reports |
| spelling | doaj-art-cfd9b1b45e224f669f555409d310fef72025-08-20T02:43:54ZengMDPI AGQuantum Reports2624-960X2024-09-016450952110.3390/quantum6040034Quantum-Enhanced Generalized Pattern Search OptimizationColton Mikes0David Huckleberry Gutman1Victoria E. Howle2Department of Industrial, Manufacturing and Systems Engineering, Texas Tech University, Lubbock, TX 79409, USADepartment of Industrial and Systems Engineering, Texas A&M, College Station, TX 77840, USADepartment of Mathematics and Statistics, Texas Tech University, Lubbock, TX 79409, USAWhile the development of quantum computers promises a myriad of advantages over their classical counterparts, care must be taken when designing algorithms that substitute a classical technique with a potentially advantageous quantum method. The probabilistic nature of many quantum algorithms may result in new behavior that could negatively impact the performance of the larger algorithm. The purpose of this work is to preserve the advantages of applying quantum search methods for generalized pattern search algorithms (GPSs) without violating the convergence criteria. It is well known that quantum search methods are able to reduce the expected number of oracle calls needed for finding the solution to a search problem from <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>N</mi><mo>)</mo></mrow></semantics></math></inline-formula> to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><msqrt><mi>N</mi></msqrt><mo>)</mo></mrow></semantics></math></inline-formula> However, the number of oracle calls needed to determine that no solution exists with certainty is exceedingly high and potentially infinite. In the case of GPS, this is a significant problem since overlooking a solution during an iteration will violate a needed assumption for convergence. Here, we overcome this problem by introducing the quantum improved point search (QIPS), a classical–quantum hybrid variant of the quantum search algorithm QSearch. QIPS retains the <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><msqrt><mi>N</mi></msqrt><mo>)</mo></mrow></semantics></math></inline-formula> oracle query complexity of QSearch when a solution exists. However, it is able to determine when no solution exists, with certainty, using only <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>N</mi><mo>)</mo></mrow></semantics></math></inline-formula> oracle calls.https://www.mdpi.com/2624-960X/6/4/34quantum computingpattern search optimizationquantum algorithmsquantum search |
| spellingShingle | Colton Mikes David Huckleberry Gutman Victoria E. Howle Quantum-Enhanced Generalized Pattern Search Optimization Quantum Reports quantum computing pattern search optimization quantum algorithms quantum search |
| title | Quantum-Enhanced Generalized Pattern Search Optimization |
| title_full | Quantum-Enhanced Generalized Pattern Search Optimization |
| title_fullStr | Quantum-Enhanced Generalized Pattern Search Optimization |
| title_full_unstemmed | Quantum-Enhanced Generalized Pattern Search Optimization |
| title_short | Quantum-Enhanced Generalized Pattern Search Optimization |
| title_sort | quantum enhanced generalized pattern search optimization |
| topic | quantum computing pattern search optimization quantum algorithms quantum search |
| url | https://www.mdpi.com/2624-960X/6/4/34 |
| work_keys_str_mv | AT coltonmikes quantumenhancedgeneralizedpatternsearchoptimization AT davidhuckleberrygutman quantumenhancedgeneralizedpatternsearchoptimization AT victoriaehowle quantumenhancedgeneralizedpatternsearchoptimization |