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 (74)
- Fault-tolerant quantum computation by anyons
- Non-Abelian Anyons and Topological Quantum Computation
- Quantum Mechanics helps in searching for a needle in a haystack
- Quantum Teleportation is a Universal Computational Primitive
- Strengths and Weaknesses of Quantum Computing
- Quantum Computation and Decision Trees
- A Theory of Fault-Tolerant Quantum Computation
- On the Power of One Bit of Quantum Information
- Exponential algorithmic speedup by quantum walk
- Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
- Robustness of adiabatic quantum computation
- Polynomial-time quantum algorithm for the simulation of chemical dynamics
- Efficient Simulation of Quantum Systems by Quantum Computers
- Entanglement and the Power of One Qubit
- A Quantum Algorithm for Finding the Minimum
- An approximate Fourier transform useful in quantum factoring
- A new quantum ripple-carry addition circuit
- The computational complexity of PEPS
- Simulation of topological field theories by quantum computers
- Adiabatic Quantum Computation in Open Systems
- Universal quantum computation using only projective measurement, quantum memory, and preparation of the 0 state
- Addition on a Quantum Computer
- A Limit on the Speed of Quantum Computation in Determining Parity
- Approximate Quantum Fourier Transform and Decoherence
- Realizable Hamiltonians for Universal Adiabatic Quantum Computers
- The quantum query complexity of the hidden subgroup problem is polynomial
- From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
- Simulations of Many-Body Quantum Systems by a Quantum Computer
- Codeword Stabilized Quantum Codes
- Fast quantum algorithm for numerical gradient estimation
- Calculating the Thermal Rate Constant with Exponential Speed-Up on a Quantum Computer
- The BQP-hardness of approximating the Jones Polynomial
- Noise resistance of adiabatic quantum computation using random matrix theory
- Exponential speed-up with a single bit of quantum information: Testing the quantum butterfly effect
- A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
- Applications of coherent classical communication and the Schur transform to quantum information theory
- Coherence-Preserving Quantum Bits
- Quantum algorithms for hidden nonlinear structures
- A new construction for a QMA complete 3-local Hamiltonian
- Trading inverses for an irrep in the Solovay-Kitaev theorem
- Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of non-abelian Groups
- The Hidden Subgroup Problem - Review and Open Problems
- Nonadditive quantum error-correcting code
- Simple proof of fault tolerance in the graph-state model
- A fast quantum mechanical algorithm for database search
- Robustness of the adiabatic quantum search
- Two-qubit Projective Measurements are Universal for Quantum Computation
- Efficient Quantum Algorithms for Estimating Gauss Sums
- Characterization of complex quantum dynamics with a scalable NMR information processor
- The quantum adiabatic search with decoherence in the instantaneous energy eigenbasis
- Efficient Quantum Algorithms for Shifted Quadratic Character Problems
- On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
- Invariant Quantum Algorithms for Insertion into an Ordered List
- Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem
- A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
- Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer
- 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
- Computation with Unitaries and One Pure Qubit
- BQP-complete Problems Concerning Mixing Properties of Classical Random Walks on Sparse Graphs
- Quantum Simulated Annealing
- Quantum Search in an Ordered List via Adaptive Learning
- Efficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups
- 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
- Notes on the hidden subgroup problem on some semi-direct product groups
- Quantum algorithms which accept hot qubit inputs
- Efficient Quantum Algorithm for Identifying Hidden Polynomials
- Quantum algorithm for the hidden subgroup problem on a class of semidirect product groups
- Estimating diagonal entries of powers of sparse symmetric matrices is BQP-complete
- 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
Cited by in corpus (16)
- Emerging quantum computing algorithms for quantum chemistry
- Optimizing quantum optimization algorithms via faster quantum gradient computation
- Quantum Algorithms for Fermionic Quantum Field Theories
- Quantum algorithm for estimating Renyi entropies of quantum states
- QMA-complete problems for stoquastic Hamiltonians and Markov matrices
- Convex optimization using quantum oracles
- Fast Quantum Methods for Optimization
- Local Hamiltonians in Quantum Computation
- Improved Bounds for Eigenpath Traversal
- Fast quantum algorithms for approximating some irreducible representations of groups
- Permutational Quantum Computing
- Programming the full stack of an open-access quantum computer
- Engineering of Anyons on M5-Probes via Flux Quantization
- Adiabatic Quantum Computation
- The quantum query complexity of learning multilinear polynomials
- Quantum algorithms for exponential sums and the evaluation of the Riemann zeta function