Adiabatic computation has been proposed as an architecture for quantum computation. In this project, we simulate an adiabatic computation de- signed to solve the MAX-2SAT problem, and study its behavior in the presence of noise. For this system, we implement a recently proposed error- correcting code (7) that is tolerant against 1-local errors. We show that the system can tolerate higher error rates using error-correction. trary to circuit model, the Hamiltonian of the sys- tem changes very slowly. One begins with a Hamil- tonian whose ground state is easy to construct, and gradually varies the Hamiltonian into one whose ground state encodes the solution to a computa- tional problem. It has been shown that the circuit model of quantum computers can be simulated by adiabatic computing (6). In this project we look at adiabatic computing in the presence of errors. We simulate a quantum adi- abatic algorithm designed to solve the NP-complete problem MAX-2SAT. We consider the in∞uence of quantum errors in the correctness probability of the algorithm. Recently, error-correcting codes speciflc for adiabatic quantum computation have been pro- posed. We implement these error-correcting codes for our particular instance of problem. We report the rate of error that these codes can tolerate.
Adiabatic computation has been proposed as an architecture for quantum computation. In this project, we simulate an adiabatic computation de- signed to solve the MAX-2SAT problem, and study its behavior in the presence of noise. For this system, we implement a recently proposed error- correcting code (7) that is tolerant against 1-local errors. We show that the system can tolerate higher error rates using error-correction. trary to circuit model, the Hamiltonian of the sys- tem changes very slowly. One begins with a Hamil- tonian whose ground state is easy to construct, and gradually varies the Hamiltonian into one whose ground state encodes the solution to a computa- tional problem. It has been shown that the circuit model of quantum computers can be simulated by adiabatic computing (6). In this project we look at adiabatic computing in the presence of errors. We simulate a quantum adi- abatic algorithm designed to solve the NP-complete problem MAX-2SAT. We consider the in∞uence of quantum errors in the correctness probability of the algorithm. Recently, error-correcting codes speciflc for adiabatic quantum computation have been pro- posed. We implement these error-correcting codes for our particular instance of problem. We report the rate of error that these codes can tolerate.
Recently, there has been growing interest in using adiabatic quantum computation as an architecture for experimentally realizable quantum computers. One of the reasons for this is the idea that the energy gap should provide some inherent resistance to noise. It is now known that universal quantum computation can be achieved adiabatically using two-local Hamiltonians. The energy gap in these Hamiltonians scales as an inverse polynomial in the number of quantum gates being simulated. Here we present stabilizer codes which can be used to produce a constant energy gap against one-local and two-local noise. The corresponding fault-tolerant universal Hamiltonians are four-local and six-local, respectively, which are the optimal result achievable within this framework.
This thesis is concerned with certain theoretical problems that arise naturally in the context of fault-tolerant quantum computation. Fault-tolerance can be defined as the art of building reliable devices from unreliable components, and is of particular importance for quantum computers that aim to precisely control the dynamics of extremely sensitive quantum systems. A model of quantum computation is a specification of the basic building blocks by which a quantum computation is implemented. The best known model is the quantum circuit model, where computations are implemented by means of unitary quantum gates that are applied to two-level quantum systems known as qubits. In a physical implementation of a quantum circuit, the gates and qubits will inevitably be affected by noise. Fault-tolerant quantum circuits are designed to be resilient against the effects of this noise, provided that it is not too strong. Fault-tolerance in the quantum circuit model is well developed thanks to the theory of quantum error-correcting codes. These codes allow for the correction of small numbers of errors introduced by a variety of noise processes. In a fault-tolerant quantum circuit, qubits are replaced with encoded qubits, and quantum gates with encoded gates that are immediately followed by special quantum circuits for error correction. Provided the rate at which errors occur is below a constant threshold value, the accumulation of errors can be checked so that the correct output of the computation correctly determined. The threshold acts as both a measure of how good the design of a quantum circuit is, and also as a target for experimenters aiming to implement quantum circuits. Much current research in quantum computation is aimed at designing quantum circuits that increase the noise threshold, hopefully to the point where it becomes within the reach of experimenters. A fault-tolerant encoded quantum gate must limit the propagation of errors so that the code’s corrective capabilities are not overwhelmed. It is not so easy to design encoded gates that satisfy this property, and to date only a finite handful of such gates are known. In a faulttolerant quantum circuit, all quantum gates must be decomposed or compiled in terms of those that may be implemented fault-tolerantly. In the first part of this thesis, we present two results that may be applied to this problem of gate compilation. The first is a generic method based on the Solovay-Kitaev theorem that may be applied to all quantum gates, but is most effective for those that act on single qubits. We present the Solovay-Kitaev theorem in its simples known form as an algorithm, together with novel constructions that can be used to implement it. Following this we give a two specialized methods for two-qubit gate decomposition, based on the Cartan decomposition of the Lie group SU(4). The cluster-state model of computation is an alternative to the quantum circuit model, and makes use of quantum measurements and highly entangled cluster-states to implement a quantum computation. The fault-tolerant techniques developed for quantum circuits are not immediately applicable in this model, so in order for it to be a realistic candidate for performing computations we prove that such techniques are possible. In the second part of the thesis we prove that constant fault-tolerance thresholds may be achieved in the cluster-state model, and in particular in an adaption to an optical implementation. Following this we design a complete error correction scheme for optical cluster-state computation, and numerically determine the threshold of this model in the face of the dominant noise models likely to affect such an implementation.
A quantum system will stay near its instantaneous ground state if the Hamiltonian that governs its evolution varies slowly enough. This quantum adiabatic behavior is the basis of a new class of algorithms for quantum computing. We tested one such algorithm by applying it to randomly generated hard instances of an NP-complete problem. For the small examples that we could simulate, the quantum adiabatic algorithm worked well, providing evidence that quantum computers (if large ones can be built) may be able to outperform ordinary computers on hard sets of instances of NP-complete problems.
Quantum computing offers powerful new techniques for speeding up the calculation of many classically intractable problems. Quantum algorithms can allow for the efficient simulation of physical systems, with applications to basic research, chemical modeling, and drug discovery; other algorithms have important implications for cryptography and internet security. At the same time, building a quantum computer is a daunting task, requiring the coherent manipulation of systems with many quantum degrees of freedom while preventing environmental noise from interacting too strongly with the system. Fortunately, we know that, under reasonable assumptions, we can use the techniques of quantum error correction and fault tolerance to achieve an arbitrary reduction in the noise level. In this thesis, we look at how additional information about the structure of noise, or "noise bias," can improve or alter the performance of techniques in quantum error correction and fault tolerance. In Chapter 2, we explore the possibility of designing certain quantum gates to be extremely robust with respect to errors in their operation. This naturally leads to structured noise where certain gates can be implemented in a protected manner, allowing the user to focus their protection on the noisier unprotected operations. In Chapter 3, we examine how to tailor error-correcting codes and fault-tolerant quantum circuits in the presence of dephasing biased noise, where dephasing errors are far more common than bit-flip errors. By using an appropriately asymmetric code, we demonstrate the ability to improve the amount of error reduction and decrease the physical resources required for error correction. In Chapter 4, we analyze a variety of protocols for distilling magic states, which enable universal quantum computation, in the presence of faulty Clifford operations. Here again there is a hierarchy of noise levels, with a fixed error rate for faulty gates, and a second rate for errors in the distilled states which decreases as the states are distilled to better quality. The interplay of of these different rates sets limits on the achievable distillation and how quickly states converge to that limit.
Quantum computers would prove a ground-breaking effect in several re- search fields to the advantage of our society due to their proved capacity for solving some problems deemed as too complex for classical comput- ers. Consequently, there is a generalized academic effort for constructing a quantum computer. Nonetheless, a real quantum computer does not suffice for implementing quantum algorithms reliably, it must be fault-tolerant. Quantum computers undergo noise due to a phenomenon generally named quantum decoherence, a fault-tolerant quantum computer has the capabil- ity to suppress the effects of decoherence to an extent. For that to happen, a quantum computer should consider quantum error correction, a process in which decoherence is studied and attempted to be corrected. Within the context of quantum error correction, the information from quantum proces- sors is to be stored in a larger, more redundant system named a quantum error correcting code. Afterwards, one can obtain a vector named syndrome which provides partial information on the effect decoherence has had on a code. The process of recovering the decoherence or error that the code has undergone is named decoding. This thesis studies decoders for quan- tum error correcting codes, their performance, complexity and adaption to different types of quantum decoherence.
The model of adiabatic quantum computation is a new paradigm for designing quantum algorithms. This model is based on the quantum adiabatic theorem, where a quantum computer evolves the quantum system slowly to switch gradually from an initial Hamiltonian with a ground state which is easy to construct, to a final Hamiltonian whose ground state encodes the solution of the problem to be solved. This dissertation presents an experimental study on the discrete quantum adiabatic computation in combinatorial search problems, we take k-Satisfiability problem as target problem to be examined. For k ? 3, k-SAT is NP-complete, i.e., among the most difficult NP problems in the worst case. Here we proposes a new monotonic variation method for the phase shift and mixing functions in the adiabatic quantum algorithm called the Quadric variation method, in order to speed up the algorithm search and decrease the overall resulting search cost. In addition, we present a better parameter configuration for the algorithm to be used with quadric variation as well as the previously proposed methods. The experiment are carried out in solving random instances of 3-SAT problems. The results indicate that the proposed method of using monotonic quadric variation in the phase functions of the adiabatic algorithm greatly improve the search behavior of the adiabatic algorithm and reduces the resulting search cost, also the results indicate that the better configuration of the algorithm parameters could greatly enhance the search behavior for the proposed method as well as the previously proposed methods.