Optimality of Quantum Adiabatic Search Algorithm and Its Circuit Model
Open Access
- 26 March 2026
- journal article
- research article
- Published by MDPI AG in Quantum Reports
- Vol. 8 (2) , 28
Abstract
In this paper, we study two aspects of quantum adiabatic evolution for a prototypical search problem: the optimality of the corresponding algorithm and its relation to the quantum circuit model. Firstly, we propose a general framework for proving the square-root speedup of the quantum adiabatic algorithm to be optimal over classical computation, which is readily applicable to the case of multiple targets. Through this framework, we also find that it is possible to further reduce the time complexity by increasing the physical energy of the system, encompassing results from previous works. Secondly, we find that, on the one hand, when the quantum adiabatic algorithm that achieves quadratic speedup is implemented on a quantum circuit, the time slice needed is always consistent with its time complexity, which also encompasses previous results; on the other hand, however, if a further algorithmic improvement is considered, the time slice always remains invariant. This phenomenon represents a significant observation with potential applications. We anticipate that the main results of this paper will interest the quantum adiabatic computation community and may help us to design efficient quantum algorithms for practical problems in the future.Keywords
Funding Information
- General Program of the Educational Commission of Anhui Province of China (KJ2021A0023)
- Research Start-up Funds of Anhui University (M080255003)
- Natural Science Research Project of Universities in Anhui Province (2024AH051383)
This publication has 47 references indexed in Scilit:
- On the quantum circuit model of a kind of quantum adiabatic evolutionQuantum Information Processing, 2025
- Enhancing IC substrate manufacturing through differential geometry and lightweight networks for etching defect detectionJournal of Manufacturing Systems, 2025
- Learning adiabatic quantum algorithms over optimization problemsQuantum Machine Intelligence, 2021
- The travelling salesman problem and adiabatic quantum computation: an algorithmQuantum Information Processing, 2019
- On the Circuit Model of Global Adiabatic Search AlgorithmInternational Journal of Theoretical Physics, 2015
- Nonadiabatic corrections to a quantum dot quantum computer working in adiabatic limitPramana, 2014
- Optimality of partial adiabatic search and its circuit modelQuantum Information Processing, 2014
- Partial adiabatic quantum search algorithm and its extensionsQuantum Information Processing, 2013
- Different Approaches for Implementing Quantum Search by Adiabatic EvolutionAASRI Procedia, 2012
- Unstructured Adiabatic Quantum SearchInternational Journal of Theoretical Physics, 2004