Quantum Computation Beyond the Circuit Model

2008/09/13 by Jordan, Stephen P. · 2 citations
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.0809.2307

openalex publication_date 2008/09/13 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

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.

Citations

• The Hidden Subgroup Problem - Review and Open Problems
• Modern Quantum Mechanics
• Two-qubit Projective Measurements are Universal for Quantum Computation
• A new quantum ripple-carry addition circuit
• Quantum algorithm for the hidden subgroup problem on a class of semidirect product groups
• Addition on a Quantum Computer
• Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of\n non-abelian Groups
• Quantum Algorithm for Commutativity Testing of a Matrix Set
• A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
• Quantum Algorithms for Lowest Weight Paths and Spanning Trees in Complete Graphs
• Quantum computation and decision trees
• Strengths and Weaknesses of Quantum Computing
• Exponential algorithmic speedup by a quantum walk
• Quantum mechanical computers
• The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling
• Fault-tolerant quantum computation by anyons
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Non-Abelian anyons and topological quantum computation
• Local Hamiltonians in Quantum Computation
• Simulating physics with computers
• A Topological Oracle Model for Proving P ≠ NP

Cited by

• Fast quantum algorithms for approximating some irreducible representations of groups
• Programming the full stack of an open-access quantum computer

Related

• Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation
• Quantum computing from a mathematical perspective: a description of the quantum circuit model
• Quantum Computation: A Computer Science Perspective
• Quantum algorithms: A survey of applications and end-to-end complexities
• Quantum Computation