Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Fourier Transform
Multi Dimensional
Related Publications
(7)
Quantum measurements and the Abelian Stabilizer Problem
PolynomialTime Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
Fast parallel circuits for the quantum Fourier transform
On the Power of Quantum Computation
An Improved Quantum Fourier Transform Algorithm and Applications
Subscribe
Academic
Publications
Quantum Fourier sampling simplified
Quantum Fourier sampling simplified,10.1145/301250.301336,Lisa Hales,Sean Hallgren
Edit
Quantum Fourier sampling simplified
(
Citations: 26
)
BibTex

RIS

RefWorks
Download
Lisa Hales
,
Sean Hallgren
We isolate and generalize a technique implicit in manyquantum algorithms, including Shor's algorithms forfactoring and discrete log. In particular, we show thatthe distribution sampled after a
Fourier transform
overZ p can be eciently approximated by transforming overZ q for any q in a large range. Our result places no restrictionson the superposition to be transformed, generalizingprevious applications. In addition, our proofeasily generalizes to multidimensional transforms forany...
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 330338, 1999
DOI:
10.1145/301250.301336
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
(
portal.acm.org
)
(
www.informatik.unitrier.de
)
(
portal.acm.org
)
More »
Citation Context
(16)
...More precisely, it is known that the distribution obtained from sampling the Fourier transformed states with respect to DFTN can be efficiently approximated by transforming with respect to DFTM, where M ≥ N. In [
20
] a detailed analysis can be found which studies how the close the resulting probability distributions are depending on M and N...
Martin Rötteler
,
et al.
Representationtheoretical properties of the approximate quantum Fouri...
...(However, since Z ∗ is unknown, Shor’s algorithm actually performs the transform over Zq where q is polynomially bounded by n; see [25] or [
10
, 11].)...
Cristopher Moore
,
et al.
The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Gr...
...Following Shor’s discovery, there has been considerable progress in showing that quantum computers can eciently solve the HSP for particular groups and particular kinds of subgroups [6, 12,
13
, 14, 15, 16, 17, 18, 19, 20, 21, 22] (although there is also evidence that some hidden subgroup problems may be hard even for quantum computers [23, 24])...
Dave Bacon
,
et al.
Optimal measurements for the dihedral hidden subgroup problem
...First, we develop a circuit for the QFT with respect to a powerof2 modulus, and then, using a technique of [
11
], we show that the QFT with respect to arbitrary moduli can be approximated too...
...The relation between quantum Fourier transforms with different moduli was described in [
11
]...
Peter Høyer
,
et al.
Quantum Fanout is Powerful
...(Note that in Shor’s algorithm, since Z n is unknown, the Fourier transform is performed over Zq for some q = poly(n); see [28] or [
10
, 11].)...
Cristopher Moore
,
et al.
The Symmetric Group Defies Strong Fourier Sampling: Part I
References
(11)
On Quantum Algorithms for Noncommutative Hidden Subgroups
(
Citations: 80
)
Mark Ettinger
,
Peter Høyer
Conference:
Symposium on Theoretical Aspects of Computer Science  STACS
, pp. 478487, 1999
Polynomialtime algorithms for prime factorization and discrete logarithms on a quantum computer
(
Citations: 5
)
Peter W. Shot
Journal:
Siam Journal on Scientific Computing
, 1997
Quantum computation of Fourier transforms over symmetric groups
(
Citations: 80
)
Robert Beals
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 4853, 1997
On the Power of Quantum Computation
(
Citations: 457
)
Daniel R. Simon
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 26, no. 5, pp. 14741483, 1997
Quantum Complexity Theory
(
Citations: 636
)
Ethan Bernstein
,
Umesh V. Vazirani
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 26, no. 5, pp. 14111473, 1997
Sort by:
Citations
(26)
Representationtheoretical properties of the approximate quantum Fourier transform
Martin Rötteler
,
Thomas Beth
Journal:
Applicable Algebra in Engineering, Communication and Computing  AAECC
, vol. 19, no. 3, pp. 177193, 2008
The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts
(
Citations: 6
)
Cristopher Moore
,
Daniel N. Rockmore
,
Alexander Russell
,
Leonard J. Schulman
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 37, no. 3, pp. 938958, 2007
Optimal measurements for the dihedral hidden subgroup problem
(
Citations: 24
)
Dave Bacon
,
Andrew M. Childs
,
Wim van Dam
Journal:
Chicago Journal of Theoretical Computer Science  CJTCS
, 2005
Fast quantum algorithms for computing the unit group and class group of a number field
(
Citations: 22
)
Sean Hallgren
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 468474, 2005
Quantum Fanout is Powerful
(
Citations: 6
)
Peter Høyer
,
Robert Spalek
Journal:
Studia Logica  An International Journal for Symbolic Logic  SLOGICA
, vol. 1, no. 1, pp. 81103, 2005