Quantum algorithms, symmetry, and Fourier analysis
Transcript Of Quantum algorithms, symmetry, and Fourier analysis
University of New Mexico
UNM Digital Repository
Physics & Astronomy ETDs
Electronic Theses and Dissertations
8-27-2012
Quantum algorithms, symmetry, and Fourier analysis
Aaron Jafar Denney
Follow this and additional works at: https://digitalrepository.unm.edu/phyc_etds
Recommended Citation
Denney, Aaron Jafar. "Quantum algorithms, symmetry, and Fourier analysis." (2012). https://digitalrepository.unm.edu/phyc_etds/ 14
This Dissertation is brought to you for free and open access by the Electronic Theses and Dissertations at UNM Digital Repository. It has been accepted for inclusion in Physics & Astronomy ETDs by an authorized administrator of UNM Digital Repository. For more information, please contact [email protected]
Aaron Denney
Candidate
Physics and Astronomy
Department
This dissertation is approved, and it is acceptable in quality and form for publication: Approved by the Dissertation Committee:
Cristopher Moore , Chairperson
Carlton Caves
Ivan Deutsch
Andrew Landahl
Quantum Algorithms, Symmetry, and Fourier Analysis
by
Aaron Denney
B.S., California Institute of Technology, 2000
DISSERTATION
Submitted in Partial Fulfillment of the Requirements for the Degree of
Doctorate of Philosophy Physics
The University of New Mexico Albuquerque, New Mexico July, 2012
iii c 2012, Aaron Denney
iv
Acknowledgments
I would like to thank my advisor, Cris Moore, whose combination of patience and prodding has been vital. I would also like to thank the many members of the UNM quantum information groups whose support and insightful conversations have contributed to my graduate experience.
v
Quantum Algorithms, Symmetry, and Fourier Analysis
by
Aaron Denney
B.S., California Institute of Technology, 2000 Ph.D., Physics, University of New Mexico, 2012
Abstract
I describe the role of symmetry in two quantum algorithms, with a focus on how that symmetry is made manifest by the Fourier transform. The Fourier transform can be considered in a wider context than the familiar one of functions on Rn or Z/nZ; instead it can be defined for an arbitrary group where it is known as representation theory.
The first quantum algorithm solves an instance of the hidden subgroup problem— distinguishing conjugates of the Borel subgroup from each other in groups related to PSL(2; q). I use the symmetry of the subgroups under consideration to reduce the problem to a mild extension of a previously solved problem. This generalizes a result of Moore, Rockmore, Russel and Schulman[33] by switching to a more natural measurement that also applies to prime powers.
In contrast to the first algorithm, the second quantum algorithm is an attempt to use naturally continuous spaces. Quantum walks have proved to be a useful tool for designing quantum algorithms. The natural equivalent to continuous time quantum walks is evolution with the Schro¨dinger equation, under the kinetic energy Hamiltonian for a massive particle. I take advantage of quantum interference to find
vi
the center of spherical shells in high dimensions. Any implementation would be likely to take place on a discrete grid, using the ability of a digital quantum computer to simulate the evolution of a quantum system.
In addition, I use ideas from the second algorithm on a different set of starting states, and find that quantum evolution can be used to sample from the evolute of a plane curve. The method of stationary phase is used to determine scaling exponents characterizing the precision and probability of success for this procedure.
vii
Contents
List of Figures
x
Glossary
xi
1 Introduction
1
2 Background
4
2.1 Classical and Quantum algorithms . . . . . . . . . . . . . . . . . . . 4
2.2 Symmetry and the Fourier transform . . . . . . . . . . . . . . . . . . 5
3 Symmetries of discrete spaces: a non-Abelian hidden subgroup
problem
7
3.1 Introduction: hidden subgroup problems . . . . . . . . . . . . . . . . 7
3.2 Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Families of transitive groups . . . . . . . . . . . . . . . . . . . . . . . 13
3.4 PSL(2; q) and some relatives . . . . . . . . . . . . . . . . . . . . . . . 14
3.5 An efficient algorithm for distinguishing the conjugates of the Borel subgroup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.6 Generalizing the affine group to prime powers . . . . . . . . . . . . . 17
Contents
viii
3.7 AGL(d; 2) and its stabilizer subgroups . . . . . . . . . . . . . . . . . 20
3.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.9 Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Symmetries of continuous spaces: finding the center of a sphere 23 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 States concentrated near surfaces, and their evolution . . . . . . . . . 28 4.3 Spherical shells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.3.1 The initial state and its evolution . . . . . . . . . . . . . . . . 30 4.3.2 A singularity at the center . . . . . . . . . . . . . . . . . . . . 32 4.3.3 Using the method of stationary phase . . . . . . . . . . . . . . 34 4.3.4 Behavior near the origin . . . . . . . . . . . . . . . . . . . . . 39 4.4 Algorithmic applications . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.4.1 Combining multiple measurements . . . . . . . . . . . . . . . 42 4.4.2 Analyzing the MLE algorithm . . . . . . . . . . . . . . . . . . 43 4.4.3 Iteration to improve estimates . . . . . . . . . . . . . . . . . . 52 4.4.4 Comparison with previous work . . . . . . . . . . . . . . . . . 58 4.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5 Applications to less symmetric spaces: sampling from evolutes 62 5.1 Curves in two dimensions . . . . . . . . . . . . . . . . . . . . . . . . 63 5.1.1 Analysis of a specific point . . . . . . . . . . . . . . . . . . . . 67 5.1.2 Width of region near the evolute . . . . . . . . . . . . . . . . 69
Contents
ix
5.1.3 Cusps—fourth order points . . . . . . . . . . . . . . . . . . . 71
5.1.4 Similar work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6 Further directions
73
A Derivations
75
A.1 Spreading of a Gaussian wave-packet via expansion in the Fourier domain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
B Stationary phase method
77
C Code
80
C.1 Box-Muller for Gaussian sampling . . . . . . . . . . . . . . . . . . . . 80
C.1.1 box muller.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
C.1.2 box muller.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
C.2 Generating samples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
C.2.1 sampled.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
C.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
C.3.1 make-estimates.c . . . . . . . . . . . . . . . . . . . . . . . . . 85
References
100
UNM Digital Repository
Physics & Astronomy ETDs
Electronic Theses and Dissertations
8-27-2012
Quantum algorithms, symmetry, and Fourier analysis
Aaron Jafar Denney
Follow this and additional works at: https://digitalrepository.unm.edu/phyc_etds
Recommended Citation
Denney, Aaron Jafar. "Quantum algorithms, symmetry, and Fourier analysis." (2012). https://digitalrepository.unm.edu/phyc_etds/ 14
This Dissertation is brought to you for free and open access by the Electronic Theses and Dissertations at UNM Digital Repository. It has been accepted for inclusion in Physics & Astronomy ETDs by an authorized administrator of UNM Digital Repository. For more information, please contact [email protected]
Aaron Denney
Candidate
Physics and Astronomy
Department
This dissertation is approved, and it is acceptable in quality and form for publication: Approved by the Dissertation Committee:
Cristopher Moore , Chairperson
Carlton Caves
Ivan Deutsch
Andrew Landahl
Quantum Algorithms, Symmetry, and Fourier Analysis
by
Aaron Denney
B.S., California Institute of Technology, 2000
DISSERTATION
Submitted in Partial Fulfillment of the Requirements for the Degree of
Doctorate of Philosophy Physics
The University of New Mexico Albuquerque, New Mexico July, 2012
iii c 2012, Aaron Denney
iv
Acknowledgments
I would like to thank my advisor, Cris Moore, whose combination of patience and prodding has been vital. I would also like to thank the many members of the UNM quantum information groups whose support and insightful conversations have contributed to my graduate experience.
v
Quantum Algorithms, Symmetry, and Fourier Analysis
by
Aaron Denney
B.S., California Institute of Technology, 2000 Ph.D., Physics, University of New Mexico, 2012
Abstract
I describe the role of symmetry in two quantum algorithms, with a focus on how that symmetry is made manifest by the Fourier transform. The Fourier transform can be considered in a wider context than the familiar one of functions on Rn or Z/nZ; instead it can be defined for an arbitrary group where it is known as representation theory.
The first quantum algorithm solves an instance of the hidden subgroup problem— distinguishing conjugates of the Borel subgroup from each other in groups related to PSL(2; q). I use the symmetry of the subgroups under consideration to reduce the problem to a mild extension of a previously solved problem. This generalizes a result of Moore, Rockmore, Russel and Schulman[33] by switching to a more natural measurement that also applies to prime powers.
In contrast to the first algorithm, the second quantum algorithm is an attempt to use naturally continuous spaces. Quantum walks have proved to be a useful tool for designing quantum algorithms. The natural equivalent to continuous time quantum walks is evolution with the Schro¨dinger equation, under the kinetic energy Hamiltonian for a massive particle. I take advantage of quantum interference to find
vi
the center of spherical shells in high dimensions. Any implementation would be likely to take place on a discrete grid, using the ability of a digital quantum computer to simulate the evolution of a quantum system.
In addition, I use ideas from the second algorithm on a different set of starting states, and find that quantum evolution can be used to sample from the evolute of a plane curve. The method of stationary phase is used to determine scaling exponents characterizing the precision and probability of success for this procedure.
vii
Contents
List of Figures
x
Glossary
xi
1 Introduction
1
2 Background
4
2.1 Classical and Quantum algorithms . . . . . . . . . . . . . . . . . . . 4
2.2 Symmetry and the Fourier transform . . . . . . . . . . . . . . . . . . 5
3 Symmetries of discrete spaces: a non-Abelian hidden subgroup
problem
7
3.1 Introduction: hidden subgroup problems . . . . . . . . . . . . . . . . 7
3.2 Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Families of transitive groups . . . . . . . . . . . . . . . . . . . . . . . 13
3.4 PSL(2; q) and some relatives . . . . . . . . . . . . . . . . . . . . . . . 14
3.5 An efficient algorithm for distinguishing the conjugates of the Borel subgroup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.6 Generalizing the affine group to prime powers . . . . . . . . . . . . . 17
Contents
viii
3.7 AGL(d; 2) and its stabilizer subgroups . . . . . . . . . . . . . . . . . 20
3.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.9 Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Symmetries of continuous spaces: finding the center of a sphere 23 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 States concentrated near surfaces, and their evolution . . . . . . . . . 28 4.3 Spherical shells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.3.1 The initial state and its evolution . . . . . . . . . . . . . . . . 30 4.3.2 A singularity at the center . . . . . . . . . . . . . . . . . . . . 32 4.3.3 Using the method of stationary phase . . . . . . . . . . . . . . 34 4.3.4 Behavior near the origin . . . . . . . . . . . . . . . . . . . . . 39 4.4 Algorithmic applications . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.4.1 Combining multiple measurements . . . . . . . . . . . . . . . 42 4.4.2 Analyzing the MLE algorithm . . . . . . . . . . . . . . . . . . 43 4.4.3 Iteration to improve estimates . . . . . . . . . . . . . . . . . . 52 4.4.4 Comparison with previous work . . . . . . . . . . . . . . . . . 58 4.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5 Applications to less symmetric spaces: sampling from evolutes 62 5.1 Curves in two dimensions . . . . . . . . . . . . . . . . . . . . . . . . 63 5.1.1 Analysis of a specific point . . . . . . . . . . . . . . . . . . . . 67 5.1.2 Width of region near the evolute . . . . . . . . . . . . . . . . 69
Contents
ix
5.1.3 Cusps—fourth order points . . . . . . . . . . . . . . . . . . . 71
5.1.4 Similar work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6 Further directions
73
A Derivations
75
A.1 Spreading of a Gaussian wave-packet via expansion in the Fourier domain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
B Stationary phase method
77
C Code
80
C.1 Box-Muller for Gaussian sampling . . . . . . . . . . . . . . . . . . . . 80
C.1.1 box muller.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
C.1.2 box muller.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
C.2 Generating samples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
C.2.1 sampled.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
C.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
C.3.1 make-estimates.c . . . . . . . . . . . . . . . . . . . . . . . . . 85
References
100