# Quantum algorithms for algebraic problems

@article{Childs2010QuantumAF, title={Quantum algorithms for algebraic problems}, author={Andrew M. Childs and Wim van Dam}, journal={Reviews of Modern Physics}, year={2010}, volume={82}, pages={1-52} }

Quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a… Expand

#### 181 Citations

Quantum algorithms for problems in number theory, algebraic geometry, and group theory

- Mathematics, Physics
- 2012

Quantum computers can execute algorithms that sometimes dramatically outperform classical computation. Undoubtedly the best-known example of this is Shor's discovery of an efficient quantum algorithm… Expand

An Efficient Deterministic Quantum Algorithm for the Integer Square-free Decomposition Problem

- Mathematics, Physics
- 2011

Quantum computers are known to be qualitatively more powerful than classical computers, but so far only a small number of different algorithms have been discovered that actually use this potential.… Expand

Quantum Computation and Isomorphism Testing

- Mathematics
- 2015

In this thesis, we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other… Expand

An Efficient Exact Quantum Algorithm for the Integer Square-free Decomposition Problem

- Computer Science, Medicine
- Scientific reports
- 2012

This work proposes an efficient and exact quantum algorithm for finding the square-free part of a large integer - a problem for which no efficient classical algorithm exists. Expand

Algorithms for Quantum Computers

- Mathematics, Computer Science
- Handbook of Natural Computing
- 2012

This paper surveys the field of quantum computer algorithms. It gives a taste of both the breadth and the depth of the known algorithms for quantum computers, focusing on some of the more recent… Expand

Quantum Computing, Quantum Games and Geometric Algebra

- Mathematics
- 2011

Early researchers attempting to simulate complex quantum mechanical interactions on digital computers discovered that they very quickly consumed the computers’ available memory resources, because the… Expand

Quantum Algorithms for Scientific Computing and Approximate Optimization

- Mathematics, Physics
- 2018

Quantum computation appears to offer significant advantages over classical computation and this has generated a tremendous interest in the field. In this thesis we consider the application of quantum… Expand

Quantum Algorithm Implementations for Beginners

- Computer Science, Physics
- ArXiv
- 2018

This review aims to explain the principles of quantum programming, which are quite different from classical programming, with straightforward algebra that makes understanding of the underlying fascinating quantum mechanical principles optional. Expand

Quantum speedup to some types of polynomial equations

- Physics, Mathematics
- 2017

In this paper, we consider three types of polynomial equations in quantum computer: linear divisibility equation, which belongs to a special type of binary-quadratic Diophantine equation; quadratic… Expand

A Survey on quantum computing technology

- Computer Science
- Comput. Sci. Rev.
- 2019

The most recent results of quantum computation technology are reviewed and the open problems of the field are addressed. Expand

#### References

SHOWING 1-10 OF 341 REFERENCES

Quantum Algorithms for Hidden Nonlinear Structures

- Computer Science
- 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)
- 2007

This work suggests an alternative generalization of the nonAbelian hidden subgroup problem, namely to problems of finding hidden nonlinear structures over finite fields, and gives examples of two such problems that can be solved efficiently by a quantum computer, but not by a classical computer. Expand

Quantum Computation and Shor's Factoring Algorithm

- Physics
- 1996

Current technology is beginning to allow us to manipulate rather than just observe individual quantum phenomena. This opens up the possibility of exploiting quantum effects to perform computations… Expand

How powerful is adiabatic quantum computation?

- Mathematics, Computer Science
- Proceedings 2001 IEEE International Conference on Cluster Computing
- 2001

It is argued that the adiabatic approach may be thought of as a kind of 'quantum local search', and a family of minimization problems that is hard for such local search heuristics are designed, and an exponential lower bound is established for the ad iabatic algorithm for these problems. Expand

Efficient Quantum Transforms

- Mathematics, Physics
- 1997

Quantum mechanics requires the operation of quantum computers to be unitary, and thus makes it important to have general techniques for developing fast quantum algorithms for computing unitary… Expand

Quantum Computational Complexity

- Mathematics, Computer Science
- Encyclopedia of Complexity and Systems Science
- 2009

Property of quantum complexity classes based on three fundamental notions: polynomial-time quantum computations, the efficient verification of quantum proofs, and quantum interactive proof systems are presented. Expand

Quantum Circuit Complexity

- Mathematics, Computer Science
- FOCS
- 1993

It is shown that any function computable in polynomial time by a quantum Turing machine has aPolynomial-size quantum circuit, and this result enables us to construct a universal quantum computer which can simulate a broader class of quantum machines than that considered by E. Bernstein and U. Vazirani (1993), thus answering an open question raised by them. Expand

Resilient quantum computation: error models and thresholds

- Mathematics, Physics
- Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences
- 1998

Recent research has demonstrated that quantum computers can solve certain types of problems substantially faster than the known classical algorithms. These problems include factoring integers and… Expand

Quantum computation of Fourier transforms over symmetric groups

- Mathematics, Computer Science
- STOC '97
- 1997

A quantum polynomial time algorithm for the Fourier transform for the symmetric groups Sn is given, adapting results obtained by Clausen and Diaconis–Rockmore to the quantum setting. Expand

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

- Computer Science, Mathematics
- SIAM Rev.
- 1999

Efficient randomized algorithms are given for factoring integers and finding discrete logarithms, two problems which are generally thought to be hard on a classical computer and have been used as the basis of several proposed cryptosystems. Expand

Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation

- Mathematics, Computer Science
- SIAM J. Comput.
- 2007

It is suggested that the adiabatic computation model and the conventional quantum computation model are polynomially equivalent and this result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. Expand