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.
Keywords
Quantum Fourier transformAbelian groupPolynomialDiscrete logarithmMathematicsQuantum algorithmQuantum phase estimation algorithmQuantum computerQuantumUnitary stateFourier transformPure mathematicsComputationElementary abelian groupDiscrete mathematicsQuantum error correctionQuantum mechanicsPhysicsComputer scienceAlgorithmMathematical analysisLaw
Affiliated Institutions
Related Publications
Quantum computations: algorithms and error correction
Contents §0. Introduction §1. Abelian problem on the stabilizer §2. Classical models of computations 2.1. Boolean schemes and sequences of operations 2.2. Reversible computation...
Strengths and Weaknesses of Quantum Computing
Recently a great deal of attention has focused on quantum computation following a sequence of results suggesting that quantum computers are more powerful than classical probabil...
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
A digital computer is generally believed to be an efficient universal computing device; that is, it is believed to be able to simulate any physical computing device with an incr...
On the power of quantum computation
The quantum model of computation is a probabilistic model, similar to the probabilistic Turing Machine, in which the laws of chance are those obeyed by particles on a quantum me...
On the Power of Quantum Computation
The quantum model of computation is a model, analogous to the probabilistic Turing machine (PTM), in which the normal laws of chance are replaced by those obeyed by particles on...
Publication Info
- Year
- 1995
- Type
- preprint
- Citations
- 512
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
512
OpenAlex
Cite This
Alexei Kitaev
(1995).
Quantum measurements and the Abelian Stabilizer Problem.
Leibniz-Zentrum für Informatik (Schloss Dagstuhl)
.
https://doi.org/10.48550/arxiv.quant-ph/9511026
Identifiers
- DOI
- 10.48550/arxiv.quant-ph/9511026