Quantum Computation Beyond the Circuit Model
arXiv:0809.2307
Abstract
The quantum circuit model is the most widely used model of quantum computation. It provides both a framework for formulating quantum algorithms and an architecture for the physical construction of quantum computers. However, several other models of quantum computation exist which provide useful alternative frameworks for both discovering new quantum algorithms and devising new physical implementations of quantum computers. In this thesis, I first present necessary background material for a general physics audience and discuss existing models of quantum computation. Then, I present three results relating to various models of quantum computation: a scheme for improving the intrinsic fault tolerance of adiabatic quantum computers using quantum error detecting codes, a proof that a certain problem of estimating Jones polynomials is complete for the one clean qubit complexity class, and a generalization of perturbative gadgets which allows k-body interactions to be directly simulated using 2-body interactions. Lastly, I discuss general principles regarding quantum computation that I learned in the course of my research, and using these principles I propose directions for future research.
Ph.D. thesis. MIT, May 2008. 144 Pages
References in corpus (24)
- Exponential algorithmic speedup by quantum walk
- A new quantum ripple-carry addition circuit
- Realizable Hamiltonians for Universal Adiabatic Quantum Computers
- From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
- Noise resistance of adiabatic quantum computation using random matrix theory
- A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
- Quantum algorithms for hidden nonlinear structures
- The Hidden Subgroup Problem - Review and Open Problems
- Simple proof of fault tolerance in the graph-state model
- Efficient Quantum Algorithms for Estimating Gauss Sums
- The quantum adiabatic search with decoherence in the instantaneous energy eigenbasis
- On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
- A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
- The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling
- Optimal quantum adversary lower bounds for ordered search
- Local Hamiltonians in Quantum Computation
- Quantum Simulated Annealing
- Quantum basin hopping with gradient-based local optimisation
- Quantum query complexity of graph connectivity
- Quantum Algorithms for Lowest Weight Paths and Spanning Trees in Complete Graphs
- Efficient Quantum Algorithm for Identifying Hidden Polynomials
- Quantum algorithm for the hidden subgroup problem on a class of semidirect product groups
- A theorem on the quantum evaluation of Weight Enumerators for a certain class of Cyclic Codes with a note on Cyclotomic cosets
- Quantum Algorithm for Commutativity Testing of a Matrix Set