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/9511026

Quantum measurements and the Abelian Stabilizer Problem

A. Yu. Kitaev

Published Nov 20, 1995• 472 citations
arXivHTMLPDF

Abstract

We present a polynomial quantum algorithm for the Abelian stabilizer problem which includes both factoring and the discrete logarithm. Thus we extend famous Shor's results. Our method is based on a procedure for measuring an eigenvalue of a unitary operator. Another application of this procedure is a polynomial quantum Fourier transform algorithm for an arbitrary finite Abelian group. The paper also contains a rather detailed introduction to the theory of quantum computation.

DOI
10.48550/arxiv.quant-ph/9511026

Related papers

Quantum measurements and the Abelian Stabilizer Problem

Alexei Kitaev

We present a polynomial quantum algorithm for the Abelian stabilizer problem which includes both factoring and the discrete logarithm. Thus we extend famous Shor's results. Our method is based on a procedure for measuring an eigenvalue of a unitary operator. Another application of this procedure is a polynomial quantum Fourier transform algorithm for an arbitrary finite Abelian group. The paper also contains a rather detailed introduction to the theory of quantum computation.

•Nov 20, 1995•442 citations

Quantum computation of Fourier transforms over symmetric groups

Robert Beals

Many algorithmic developments in quantum complexity theory, including Shor's celebrated algorithms for factoring and discrete logs, have made use of Fourier transforms over abelian groups.That is, at some point in the computation, the macline is in a superposition of states corresponding to elements of a finite abelian group G, and in quantum polynomial time (i.e., polynomial in log IGI), the machine is transformed according to the Fourier transform to a superposition of states corresponding to the irreducible representations of G.We give a quantum polynomial time algorithm for the Fourier transform for the symmetric groups Sn, adapting results obtained by Clausen and Diaconis-Rockmore to the quantum setting.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1997•140 citations

The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem

Lisa Hales

The quantum Fourier transform (QFT) has emerged as the primary tool in quantum algorithms which achieve exponential advantage over classical computation and lies at the heart of the solution to the abelian hidden subgroup problem, of which Shor's celebrated factoring and discrete log algorithms are a special case. We begin by addressing various computational issues surrounding the QFT and give improved parallel circuits for both the QFT over a power of 2 and the QFT over an arbitrary cyclic group. These circuits are based on new insight into the relationship between the discrete Fourier transform over different cyclic groups. We then exploit this insight to extend the class of hidden subgroup problems with efficient quantum solutions. First we relax the condition that the underlying hidden subgroup function be distinct on distinct cosets of the subgroup in question and show that this relaxation can be solved whenever G is a finitely-generated abelian group. We then extend this reasoning to the hidden cyclic subgroup problem over the reals, showing how to efficiently generate the bits of the period of any sufficiently piecewise-continuous function on R. Finally, we show that this problem of period-finding over R, viewed as an oracle promise problem, is strictly harder than its integral counterpart. In particular, period-finding over R lies outside the complexity class MA, a class which contains period-finding over the integers.

arXiv:quant-ph/0212002•Nov 30, 2002•25 citations

Quantum Fourier Transform and Related Algorithms

Santanu Pattanayak

In this chapter, we will study the quantum Fourier transform and its application in different quantum algorithms. Problems such as factoring an integer into prime numbers or period finding are computationally intractable problems for a classical computer because of the exponentially large number of operations involved. Integer factoring and period finding can be efficiently solved using the quantum phase estimation algorithm that is heavily based on the quantum Fourier transform. Alternately, since quantum phase estimation aims to find the eigenvalue corresponding to an eigenvector of a unitary operator, it is backbone of important algorithms in optimization such as the HHL algorithm (named for Hassim, Harrow, and Lloyd), which serves as the matrix inversion routine in quantum computing. We start this chapter by revising our concepts of the Fourier transform and its discrete counterpart, the discrete Fourier transform , and then move on to the exciting domain of the quantum Fourier transform and the quantum phase estimation algorithm. We follow this up with a discussion and implementation of the few quantum Fourier transform–related algorithms such as factoring a number and period finding. At the end of the chapter, we briefly introduce the basics of group theory with an attempt to explain the hidden subgroup problem and how it relates to several of the Fourier transform–based algorithms.

Apress eBooks•Jan 1, 2021•0 citations

The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer

Michele Mosca, ARTUR K. EKERT

A quantum computer can efficiently find the order of an element in a group, factors of composite integers, discrete logarithms, stabilisers in Abelian groups, and `hidden' or `unknown' subgroups of Abelian groups. It is already known how to phrase the first four problems as the estimation of eigenvalues of certain unitary operators. Here we show how the solution to the more general Abelian `hidden subgroup problem' can also be described and analysed as such. We then point out how certain instances of these problems can be solved with only one control qubit, or `flying qubits', instead of entire registers of control qubits.

arXiv:quant-ph/9903071•Mar 20, 1999•33 citations

Factoring Algorithms Based on NMR Quantum Computers (Computer Algebra : Algorithms, Implementations and Applications)

Noboru Kunihiro, Shigeru Yamashita

No polynomial time algorithms have been proposed for the factoring and discrete logarithm problems.However, Shor showed that these problems can be solved by aquantum Turing machine in 1994.Sev- eral devices have been proposed toward the realization of quantum computers.Among them, the NMR quantum computer seems to be the nearest to the target goal.Since the NMR quantum computer has different features from ordinary ones, we cannot directly implement Shor's algorithms.In this paper, we propose new simple algorithms that work on NMR quantum computers to solve the factoring and discrete logarithm problems.

数理解析研究所講究録•Nov 1, 2002•1 citation
We present a polynomial quantum algorithm for the Abelian stabilizer problem which includes both factoring and the discrete logarithm. Thus we extend famous Shor's results. Our method is based on a procedure for measuring an eigenvalue of a unitary operator. Another application of this procedure is a polynomial quantum Fourier transform algorithm for an arbitrary finite Abelian group. The paper also contains a rather detailed introduction to the theory of quantum computation.
Many algorithmic developments in quantum complexity theory, including Shor's celebrated algorithms for factoring and discrete logs, have made use of Fourier transforms over abelian groups.That is, at some point in the computation, the macline is in a superposition of states corresponding to elements of a finite abelian group G, and in quantum polynomial time (i.e., polynomial in log IGI), the machine is transformed according to the Fourier transform to a superposition of states corresponding to the irreducible representations of G.We give a quantum polynomial time algorithm for the Fourier transform for the symmetric groups Sn, adapting results obtained by Clausen and Diaconis-Rockmore to the quantum setting.
The quantum Fourier transform (QFT) has emerged as the primary tool in quantum algorithms which achieve exponential advantage over classical computation and lies at the heart of the solution to the abelian hidden subgroup problem, of which Shor's celebrated factoring and discrete log algorithms are a special case. We begin by addressing various computational issues surrounding the QFT and give improved parallel circuits for both the QFT over a power of 2 and the QFT over an arbitrary cyclic group. These circuits are based on new insight into the relationship between the discrete Fourier transform over different cyclic groups. We then exploit this insight to extend the class of hidden subgroup problems with efficient quantum solutions. First we relax the condition that the underlying hidden subgroup function be distinct on distinct cosets of the subgroup in question and show that this relaxation can be solved whenever G is a finitely-generated abelian group. We then extend this reasoning to the hidden cyclic subgroup problem over the reals, showing how to efficiently generate the bits of the period of any sufficiently piecewise-continuous function on R. Finally, we show that this problem of period-finding over R, viewed as an oracle promise problem, is strictly harder than its integral counterpart. In particular, period-finding over R lies outside the complexity class MA, a class which contains period-finding over the integers.
In this chapter, we will study the quantum Fourier transform and its application in different quantum algorithms. Problems such as factoring an integer into prime numbers or period finding are computationally intractable problems for a classical computer because of the exponentially large number of operations involved. Integer factoring and period finding can be efficiently solved using the quantum phase estimation algorithm that is heavily based on the quantum Fourier transform. Alternately, since quantum phase estimation aims to find the eigenvalue corresponding to an eigenvector of a unitary operator, it is backbone of important algorithms in optimization such as the HHL algorithm (named for Hassim, Harrow, and Lloyd), which serves as the matrix inversion routine in quantum computing. We start this chapter by revising our concepts of the Fourier transform and its discrete counterpart, the discrete Fourier transform , and then move on to the exciting domain of the quantum Fourier transform and the quantum phase estimation algorithm. We follow this up with a discussion and implementation of the few quantum Fourier transform–related algorithms such as factoring a number and period finding. At the end of the chapter, we briefly introduce the basics of group theory with an attempt to explain the hidden subgroup problem and how it relates to several of the Fourier transform–based algorithms.
A quantum computer can efficiently find the order of an element in a group, factors of composite integers, discrete logarithms, stabilisers in Abelian groups, and `hidden' or `unknown' subgroups of Abelian groups. It is already known how to phrase the first four problems as the estimation of eigenvalues of certain unitary operators. Here we show how the solution to the more general Abelian `hidden subgroup problem' can also be described and analysed as such. We then point out how certain instances of these problems can be solved with only one control qubit, or `flying qubits', instead of entire registers of control qubits.
No polynomial time algorithms have been proposed for the factoring and discrete logarithm problems.However, Shor showed that these problems can be solved by aquantum Turing machine in 1994.Sev- eral devices have been proposed toward the realization of quantum computers.Among them, the NMR quantum computer seems to be the nearest to the target goal.Since the NMR quantum computer has different features from ordinary ones, we cannot directly implement Shor's algorithms.In this paper, we propose new simple algorithms that work on NMR quantum computers to solve the factoring and discrete logarithm problems.