Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0606015 · Physical Review A

Majorization in quantum adiabatic algorithms

Zhaohui Wei, Zhengfeng Ji, Mingsheng Ying

Published Oct 18, 2006• 1 citation
arXivHTMLPDF

Abstract

The majorization theory has been applied to analyze the mathematical structure of quantum algorithms. An empirical conclusion by numerical simulations obtained in the previous literature indicates that step-by-step majorization seems to appear universally in quantum adiabatic algorithms. In this paper, a rigorous analysis of the majorization arrow in a special class of quantum adiabatic algorithms is carried out. In particular, we prove that for any adiabatic algorithm of this class, step-by-step majorization of the ground state holds exactly. For the actual state, we show that step-by-step majorization holds approximately, and furthermore that the longer the running time of the algorithm, the better the approximation.

DOI
10.1103/physreva.74.042320

Related papers

Majorization arrow in quantum-algorithm design

José Ignacio Latorre, Miguel Angel Martin-Delgado

We apply majorization theory to study the quantum algorithms known so far and find that there is a majorization principle underlying the way they operate. Grover's algorithm is a neat instance of this principle where majorization works step by step until the optimal target state is found. Extensions of this situation are also found in algorithms based in quantum adiabatic evolution and the family of quantum phase-estimation algorithms, including Shor's algorithm. We state that in quantum algorithms the time arrow is a majorization arrow.

arXiv:quant-ph/0111146•Physical Review A•Aug 9, 2002•34 citations

Quantum adiabatic computation and adiabatic conditions

Zhaohui Wei, Mingsheng Ying

Recently, quantum adiabatic computation has attracted more and more attention in the literature. It is a novel quantum computation model based on adiabatic approximation, and the analysis of a quantum adiabatic algorithm depends highly on the adiabatic conditions. However, it has been pointed out that the traditional adiabatic conditions are problematic. Thus, results obtained previously should be checked and sufficient adiabatic conditions applicable to adiabatic computation should be proposed. Based on a result of Tong et al. [Phys. Rev. Lett. 98, 150402 (2007)], we propose a modified adiabatic criterion which is more applicable to the analysis of adiabatic algorithms. As an example, we prove the validity of the local adiabatic search algorithm by employing our criterion.

Physical Review A•Aug 22, 2007•31 citations

Dynamics of adiabatic quantum search

Artem Pimachev

We describe a class of the Hamiltonians, for which the local adiabaticity condition is satisfied automatically. We consider the controllable adiabatic interpolations between the initial and final Hamiltonians. We show that the quantum search by the adiabatic quantum computation can be mapped into this class. Assuming that the interpolation is infinitely differentiable and the target adiabatic ground state is nondegenerate and separated by a gap from the rest of the spectrum, it is shown that one can obtain an exponentially small error in the algorithm run time T betweenthe finale adiabatic eigenstate and the actual state of the system. The optimal for quantum search scaling of T as square root of the system size is also satisfied.

•Jan 1, 2015•0 citations

INTRODUCING ADIABATIC QUANTUM COMPUTATION

Huazhong Li

Recent applications of quantum adiabatic approximation to quantum computation are reviewed.We discuss the adiabatic quantum algorithm and the recent discovery of inconsistency of quantum adiabatic theorem giving impact to this application.

Progress in physics•Jan 1, 2008•0 citations

Scaling of the running time of the quantum adiabatic algorithm for propositional satisfiability

Marko Žnidarič

We numerically study the quantum adiabatic algorithm for propositional satisfiability. A new class of previously unknown hard instances is identified among random problems. We numerically find that the running time for such instances grows exponentially with their size. The worst case complexity of the quantum adiabatic algorithm therefore seems to be exponential.

arXiv:quant-ph/0502077•Physical Review A•Jun 8, 2005•37 citations

On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms

Eliot Kapit, Brandon Barton, Sean Feeney +5 more

A canonical feature of the constraint satisfaction problems in NP is approximation hardness, where in the worst case, finding sufficient-quality approximate solutions is exponentially hard for all known methods. Fundamentally, the lack of any guided local minimum escape method ensures both exact and approximate classical approximation hardness, but the equivalent mechanism(s) for quantum algorithms are poorly understood. For algorithms based on Hamiltonian time evolution, we explore this question through the prototypically hard MAX-3-XORSAT problem class. We conclude that the mechanisms for quantum exact and approximation hardness are fundamentally distinct. We review known results from the literature, and identify mechanisms that make conventional quantum methods (such as Adiabatic Quantum Computing) weak approximation algorithms in the worst case. We construct a family of spectrally filtered quantum algorithms that escape these issues, and develop analytical theories for their performance. We show that, for random hypergraphs in the approximation-hard regime, if we define the energy to be $E = N_{\mathrm{unsat}}-N_{\mathrm{sat}}$, spectrally filtered quantum optimization will return states with $E \leq q_m E_{\mathrm{GS}}$ (where $E_{\rm GS}$ is the ground state energy) in sub-quadratic time, where conservatively, $q_m \simeq 0.59$. This is in contrast to $q_m \to 0$ for the hardest instances with classical searches. We test all of these claims with extensive numerical simulations. We do not claim that this approximation guarantee holds for all possible hypergraphs, though our algorithm's mechanism can likely generalize widely. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed.

arXiv:2312.06104•Dec 11, 2023•7 citations
The majorization theory has been applied to analyze the mathematical structure of quantum algorithms. An empirical conclusion by numerical simulations obtained in the previous literature indicates that step-by-step majorization seems to appear universally in quantum adiabatic algorithms. In this paper, a rigorous analysis of the majorization arrow in a special class of quantum adiabatic algorithms is carried out. In particular, we prove that for any adiabatic algorithm of this class, step-by-step majorization of the ground state holds exactly. For the actual state, we show that step-by-step majorization holds approximately, and furthermore that the longer the running time of the algorithm, the better the approximation.
We apply majorization theory to study the quantum algorithms known so far and find that there is a majorization principle underlying the way they operate. Grover's algorithm is a neat instance of this principle where majorization works step by step until the optimal target state is found. Extensions of this situation are also found in algorithms based in quantum adiabatic evolution and the family of quantum phase-estimation algorithms, including Shor's algorithm. We state that in quantum algorithms the time arrow is a majorization arrow.
Recently, quantum adiabatic computation has attracted more and more attention in the literature. It is a novel quantum computation model based on adiabatic approximation, and the analysis of a quantum adiabatic algorithm depends highly on the adiabatic conditions. However, it has been pointed out that the traditional adiabatic conditions are problematic. Thus, results obtained previously should be checked and sufficient adiabatic conditions applicable to adiabatic computation should be proposed. Based on a result of Tong et al. [Phys. Rev. Lett. 98, 150402 (2007)], we propose a modified adiabatic criterion which is more applicable to the analysis of adiabatic algorithms. As an example, we prove the validity of the local adiabatic search algorithm by employing our criterion.
We describe a class of the Hamiltonians, for which the local adiabaticity condition is satisfied automatically. We consider the controllable adiabatic interpolations between the initial and final Hamiltonians. We show that the quantum search by the adiabatic quantum computation can be mapped into this class. Assuming that the interpolation is infinitely differentiable and the target adiabatic ground state is nondegenerate and separated by a gap from the rest of the spectrum, it is shown that one can obtain an exponentially small error in the algorithm run time T betweenthe finale adiabatic eigenstate and the actual state of the system. The optimal for quantum search scaling of T as square root of the system size is also satisfied.
A canonical feature of the constraint satisfaction problems in NP is approximation hardness, where in the worst case, finding sufficient-quality approximate solutions is exponentially hard for all known methods. Fundamentally, the lack of any guided local minimum escape method ensures both exact and approximate classical approximation hardness, but the equivalent mechanism(s) for quantum algorithms are poorly understood. For algorithms based on Hamiltonian time evolution, we explore this question through the prototypically hard MAX-3-XORSAT problem class. We conclude that the mechanisms for quantum exact and approximation hardness are fundamentally distinct. We review known results from the literature, and identify mechanisms that make conventional quantum methods (such as Adiabatic Quantum Computing) weak approximation algorithms in the worst case. We construct a family of spectrally filtered quantum algorithms that escape these issues, and develop analytical theories for their performance. We show that, for random hypergraphs in the approximation-hard regime, if we define the energy to be E=Nunsat−NsatE = N_{\mathrm{unsat}}-N_{\mathrm{sat}}E=Nunsat​−Nsat​, spectrally filtered quantum optimization will return states with E≤qmEGSE \leq q_m E_{\mathrm{GS}}E≤qm​EGS​ (where EGSE_{\rm GS}EGS​ is the ground state energy) in sub-quadratic time, where conservatively, qm≃0.59q_m \simeq 0.59qm​≃0.59. This is in contrast to qm→0q_m \to 0qm​→0 for the hardest instances with classical searches. We test all of these claims with extensive numerical simulations. We do not claim that this approximation guarantee holds for all possible hypergraphs, though our algorithm's mechanism can likely generalize widely. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed.