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:1408.1968

More period finding with adiabatic quantum computation

Richard H. Warren

Published Aug 8, 2014• 1 citation
arXivHTMLPDF

Abstract

We extend the work of Hen for the Bernstein-Vazirani problem and Simon's problem on an adiabatic quantum computer. Our results are based on the Ising objective function for quantum annealing. For each problem we determine its objective function, describe its Hamiltonian matrix, and show the Hamiltonian matrix for a small problem. Following the pattern of Hen, we discuss factoring of integers, particularly Shor's factoring algorithm in an adiabatic quantum computing environment.

DOI
10.48550/arxiv.1408.1968

Related papers

Period finding with adiabatic quantum computation

Itay Hen

We outline an efficient quantum-adiabatic algorithm that solves Simon's problem, in which one has to determine the `period', or xor-mask, of a given black-box function. We show that the proposed algorithm is exponentially faster than its classical counterpart and has the same complexity as the corresponding circuit-based algorithm. Together with other related studies, this result supports a conjecture that the complexity of adiabatic quantum computation is equivalent to the circuit-based computational model in a stronger sense than the well-known, proven polynomial equivalence between the two paradigms. We also discuss the importance of the algorithm and its theoretical and experimental implications for the existence of an adiabatic version of Shor's integer factorization algorithm that would have the same complexity as the original algorithm.

arXiv:1307.6538•Europhysics Letters (EPL)•Mar 1, 2014•26 citations

Quantum adiabatic algorithms using unitary interpolation*

Shuo Zhang, Qian-Heng Duan, Tan Li +4 more

We present two efficient quantum adiabatic algorithms for Bernstein–Vazirani problem and Simon’s problem. We show that the time complexities of the algorithms for Bernstein–Vazirani problem and Simon’s problem are O(1) and O(n), respectively, which are the same complexities as the corresponding algorithms in quantum circuit model. In these two algorithms, the adiabatic Hamiltonians are realized by unitary interpolation instead of standard linear interpolation. Comparing with the adiabatic algorithms using linear interpolation, the energy gaps of our algorithms keep constant. Therefore, the complexities are much easier to analyze using this method.

Chinese Physics B•Dec 5, 2019•3 citations

Fourier-transforming with quantum annealers

Itay Hen

We introduce a set of quantum adiabatic evolutions that we argue may be used as `building blocks', or subroutines, in the onstruction of an adiabatic algorithm that executes Quantum Fourier Transform (QFT) with the same complexity and resources as its gate-model counterpart. One implication of the above construction is the theoretical feasibility of implementing Shor's algorithm for integer factorization in an optimal manner, and any other algorithm that makes use of QFT, on quantum annealing devices. We discuss the possible advantages, as well as the limitations, of the proposed approach as well as its relation to traditional adiabatic quantum computation.

Frontiers in Physics•Jul 28, 2014•10 citations

Breaking RSA encryption

N. David Mermin

Period finding, factoring, and cryptography Simon's problem (Section 2.5) starts with a subroutine that calculates a function f(x) , which satisfies f(x) = f(y) for distinct x and y if and only if y = x ⊕ a , where ⊕ denotes the bitwise modulo-2 sum of the n -bit integers a and x . The number of times a classical computer must invoke the subroutine to determine a grows exponentially with n , but with a quantum computer it grows only linearly. This is a rather artificial example, of interest primarily because it gives a simple demonstration of the remarkable computational power a quantum computer can possess. It amounts to finding the unknown period a of a function on n -bit integers that is “periodic” under bitwise modulo-2 addition. A more difficult, but much more natural problem is to find the period r of a function f on the integers that is periodic under ordinary addition, satisfying f(x) = f(y) for distinct x and y if and only if x and y differ by an integral multiple of r . Finding the period of such a periodic function turns out to be the key to factoring products of large prime numbers, a mathematically natural problem with quite practical applications.

Cambridge University Press eBooks•Aug 30, 2007•0 citations

Quantum algorithms 1

Helmut Bez, Tony Croft

The quantum algorithms covered in this chapter, i.e., the Deutsch, Deutsch-Jozsa and Bernstein-Vazirani algorithms, have been chosen for their relative simplicity and theoretical interest. They do not address problems of real practical value, their purpose being to demonstrate, using simple examples, the great potential power of quantum computation relative to the digital case. The most significant breakthrough in quantum computing is Shor's integer factorisation algorithm. Shor's algorithm is beyond the scope of this introductory text, but its significance lies in the fact that it demonstrates the potential to factor large integers efficiently. No efficient digital algorithms for factoring large integers exist, and many current encryption algorithms rely on this being the case. Shor's algorithm therefore threatens current encryption methods, and is responsible for much of the recent accelerated interest in quantum computation.

Chapman & Hall/CRC eBooks•Jan 6, 2023•0 citations

A Period-Finding Method for Shor's Algorithm

Weiqiang Zhang, Chen Xu, Feipeng Li +1 more

Shor's algorithm is a significant quantum algorithm for factoring a number N. The key technique of the Shor's algo- rithm is turning the factoring problem into the problem of finding the period of a function. Based on the key technique and the monotony of the mode function, an approach how to determine the period of a function is introduced. Mean- while an important parameter selection for period-finding is optimized. Several experiments discussed imply that the approach and the parameter selection are both rigorous.

International Conference on Computational Intelligence and Security (CIS)•Dec 1, 2007•7 citations
We extend the work of Hen for the Bernstein-Vazirani problem and Simon's problem on an adiabatic quantum computer. Our results are based on the Ising objective function for quantum annealing. For each problem we determine its objective function, describe its Hamiltonian matrix, and show the Hamiltonian matrix for a small problem. Following the pattern of Hen, we discuss factoring of integers, particularly Shor's factoring algorithm in an adiabatic quantum computing environment.
We outline an efficient quantum-adiabatic algorithm that solves Simon's problem, in which one has to determine the `period', or xor-mask, of a given black-box function. We show that the proposed algorithm is exponentially faster than its classical counterpart and has the same complexity as the corresponding circuit-based algorithm. Together with other related studies, this result supports a conjecture that the complexity of adiabatic quantum computation is equivalent to the circuit-based computational model in a stronger sense than the well-known, proven polynomial equivalence between the two paradigms. We also discuss the importance of the algorithm and its theoretical and experimental implications for the existence of an adiabatic version of Shor's integer factorization algorithm that would have the same complexity as the original algorithm.
We present two efficient quantum adiabatic algorithms for Bernstein–Vazirani problem and Simon’s problem. We show that the time complexities of the algorithms for Bernstein–Vazirani problem and Simon’s problem are O(1) and O(n), respectively, which are the same complexities as the corresponding algorithms in quantum circuit model. In these two algorithms, the adiabatic Hamiltonians are realized by unitary interpolation instead of standard linear interpolation. Comparing with the adiabatic algorithms using linear interpolation, the energy gaps of our algorithms keep constant. Therefore, the complexities are much easier to analyze using this method.
We introduce a set of quantum adiabatic evolutions that we argue may be used as `building blocks', or subroutines, in the onstruction of an adiabatic algorithm that executes Quantum Fourier Transform (QFT) with the same complexity and resources as its gate-model counterpart. One implication of the above construction is the theoretical feasibility of implementing Shor's algorithm for integer factorization in an optimal manner, and any other algorithm that makes use of QFT, on quantum annealing devices. We discuss the possible advantages, as well as the limitations, of the proposed approach as well as its relation to traditional adiabatic quantum computation.
Period finding, factoring, and cryptography Simon's problem (Section 2.5) starts with a subroutine that calculates a function f(x) , which satisfies f(x) = f(y) for distinct x and y if and only if y = x ⊕ a , where ⊕ denotes the bitwise modulo-2 sum of the n -bit integers a and x . The number of times a classical computer must invoke the subroutine to determine a grows exponentially with n , but with a quantum computer it grows only linearly. This is a rather artificial example, of interest primarily because it gives a simple demonstration of the remarkable computational power a quantum computer can possess. It amounts to finding the unknown period a of a function on n -bit integers that is “periodic” under bitwise modulo-2 addition. A more difficult, but much more natural problem is to find the period r of a function f on the integers that is periodic under ordinary addition, satisfying f(x) = f(y) for distinct x and y if and only if x and y differ by an integral multiple of r . Finding the period of such a periodic function turns out to be the key to factoring products of large prime numbers, a mathematically natural problem with quite practical applications.
The quantum algorithms covered in this chapter, i.e., the Deutsch, Deutsch-Jozsa and Bernstein-Vazirani algorithms, have been chosen for their relative simplicity and theoretical interest. They do not address problems of real practical value, their purpose being to demonstrate, using simple examples, the great potential power of quantum computation relative to the digital case. The most significant breakthrough in quantum computing is Shor's integer factorisation algorithm. Shor's algorithm is beyond the scope of this introductory text, but its significance lies in the fact that it demonstrates the potential to factor large integers efficiently. No efficient digital algorithms for factoring large integers exist, and many current encryption algorithms rely on this being the case. Shor's algorithm therefore threatens current encryption methods, and is responsible for much of the recent accelerated interest in quantum computation.
Shor's algorithm is a significant quantum algorithm for factoring a number N. The key technique of the Shor's algo- rithm is turning the factoring problem into the problem of finding the period of a function. Based on the key technique and the monotony of the mode function, an approach how to determine the period of a function is introduced. Mean- while an important parameter selection for period-finding is optimized. Several experiments discussed imply that the approach and the parameter selection are both rigorous.