Using simulation to assess the feasibility of quantum computing

Alvin M. Despain, Kevin Obenland

Published Jan 1, 1998• 3 citations

Abstract

Quantum computation is a new technology with the potential for providing exponential parallelism. The feasibility of a quantum computer is limited by two different types of errors, decoherence and inaccuracies. This dissertation uses simulation to investigate the feasibility of implementing one of the proposed realizations of a quantum computer, the trapped ion quantum computer. Because of the exponential complexity of a quantum computer, simulating one requires vast processing and memory resources. For this reason I develop several techniques to reduce the complexity of simulating a quantum computer. A parallel simulator is also used. Using the parallel simulator I am able to simulate circuits with close to 100,000 basic operations. The simulation studies show that the effectiveness of a quantum computer, without a mechanism for controlling errors, is severely limited. However the power of a quantum computer can be increased by using several techniques to mitigate the effects of error. Therefore a realizable quantum computer has three fundamental requirements: First, both hardware and software mechanisms must be used to correct errors as they occur. Second, the architecture of a quantum computer is very important; it must be designed to mitigate errors and it must be able to execute multiple operations in parallel. Last, quantum circuits must be constructed in an efficient manner, to minimize the total number of operations.

Related papers

A Parallel Quantum Computer Simulator

Kevin Obenland, Alvin M. Despain

A Quantum Computer is a new type of computer which can efficiently solve complex problems such as prime factorization. A quantum computer threatens the security of public key encryption systems because these systems rely on the fact that prime factorization is computationally difficult. Errors limit the effectiveness of quantum computers. Because of the exponential nature of quantum com puters, simulating the effect of errors on them requires a vast amount of processing and memory resources. In this paper we describe a parallel simulator which accesses the feasibility of quantum computers. We also derive and validate an analytical model of execution time for the simulator, which shows that parallel quantum computer simulation is very scalable.

arXiv:quant-ph/9804039Apr 16, 199852 citations

Simulating the Effect of Decoherence and Inaccuracies on a Quantum Computer

Kevin Obenland, Alvin M. Despain

A Quantum Computer is a new type of computer which can solve problems such as factoring and database search very efficiently. The usefulness of a quantum computer is limited by the effect of two different types of errors, decoherence and inaccuracies. In this paper we show the results of simulations of a quantum computer which consider both decoherence and inaccuracies. We simulate circuits which factor the numbers 15, 21, 35, and 57 as well as circuits which use database search to solve the circuit satisfaction problem. Our simulations show that the error rate per gate is on the order of 10^-6 for a trapped ion quantum computer whose noise is kept below pi/4096 per gate and with a decoherence rate of 10^-6. This is an important bound because previous studies have shown that a quantum computer can factor more efficiently than a classical computer if the error rate is of order 10^-6.

arXiv:quant-ph/9804038Apr 16, 19983 citations

Models to Reduce the Complexity of Simulating a Quantum Computer

Kevin Obenland, Alvin M. Despain

Recently Quantum Computation has generated a lot of interest due to the discovery of a quantum algorithm which can factor large numbers in polynomial time. The usefulness of a quantum com puter is limited by the effect of errors. Simulation is a useful tool for determining the feasibility of quantum computers in the presence of errors. The size of a quantum computer that can be simulat ed is small because faithfully modeling a quantum computer requires an exponential amount of storage and number of operations. In this paper we define simulation models to study the feasibility of quantum computers. The most detailed of these models is based directly on a proposed imple mentation. We also define less detailed models which are exponentially less complex but still pro duce accurate results. Finally we show that the two different types of errors, decoherence and inaccuracies, are uncorrelated. This decreases the number of simulations which must be per formed.

arXiv:quant-ph/9712004Dec 2, 19973 citations

A foundation for quantum programming and its highly-parallel virtual execution

Yves Vandriessche

The topic of this dissertation stands at the crossroads of two emerging technologies: highly-parallel computing and quantum computing. Both seek to go beyond the limits of current computing practice: in the absence of further miniaturization, highly-parallel computing seeks to increase the available computer power substantially. Quantum Computing looks beyond the classical approach to computation, leveraging quantum-mechanical effects to increase computing power in a fundamental way. In the absence and also in the presence of actual quantum computers it is crucial to support the development of quantum computer applications by creating an appropriate software framework. Creating such a framework currently faces two major research challenges. First, one needs to separate the realization of the quantum computer from the software running on it, whether it is an actual physical or a simulated realization. Our first contribution lies with defining a layered software architecture, ranging from a design tool at the higher abstraction levels to a simulated execution layer underneath. At its core sits a ‘Quantum Virtual Machine’ using the Measurement Calculus as the underlying quantum computational model. Such a virtual machine layer makes the application developed on top of it oblivious to how it is executed. The simulated execution of this quantum virtual machine is fundamentally a computationally intensive task. Parallel computing offers a way to throw more computational resources at the problem, in the light of the saturation of sequential performance of current computers. Simulation is the domain of the second challenge, as it has very high performance requirements. The simulation problem thus becomes: how does one expose the inherent parallelism of quantum computing simulation in a fundamental way, so as to be usable for the highly-parallel computers to come? Our second contribution is to provide a formal translation of quantum programs to highly-parallel dataflow computations, and to develop a virtual environment that compiles and executes such programs. This work demonstrates several properties of both the formal as well as the virtual level of computation that validate our approach.

Jan 1, 20120 citations

Methods for universal fault-tolerant quantum computation in small devices

Colin J. Trout

A reliable large-scale quantum computer would be able to solve problems in physics and chemistry exponentially faster than current classical processors. A large-scale quantum device has not been built because quantum systems are naturally sensitive to environmental influences which manifest as errors in memory and operations during computation. For a large-scale device to become a reality, protocols must be developed that reduce the influence of errors during computation in a manner that maintains scalability of the device. This scalability criteria requires the protocols developed to handle errors must be implemented in a way such that the size of the quantum system and number of operations grows in a tractable manner. Furthermore, the sources of errors must be modeled accurately for true assessments of the viability of these protocols. In this dissertation, we present an investigation into methods of performing reliable quantum computation in the presence of errors in small quantum systems (< 50 qubits). These methods should be considered as software primitives used to built reliable large-scale quantum algorithms and quantum memories. These methods occur in two flavors: quantum error correction and fault-tolerant operations. For quantum error correction, we perform assessments of error correction in the presence of error sources indicative of ion trap quantum computers. For fault-tolerant operations, we investigate the quantum resource cost and efficacy of implementing various techniques for performing reliable operations that would allow for a quantum advantange in a large-scale device.

Jan 22, 20180 citations

Architecture Framework for Trapped-Ion Quantum Computer based on Performance Simulation Tool

Muhammad Ahsan

The challenge of building scalable quantum computer lies in striking appropriate balance between designing a reliable system architecture from large number of faulty computational resources and improving the physical quality of system components. The detailed investigation of performance variation with physics of the components and the system architecture requires adequate performance simulation tool. In this thesis we demonstrate a software tool capable of (1) mapping and scheduling the quantum circuit on a realistic quantum hardware architecture with physical resource constraints, (2) evaluating the performance metrics such as the execution time and the success probability of the algorithm execution, and (3) analyzing the constituents of these metrics and visualizing resource utilization to identify system components which crucially define the overall performance. Using this versatile tool, we explore vast design space for modular quantum computer architecture based on trapped ions. We find that while success probability is uniformly determined by the fidelity of physical quantum operation, the execution time is a function of system resources invested at various layers of design hierarchy. At physical level, the number of lasers performing quantum gates, impact the latency of the fault-tolerant circuit blocks execution. When these blocks are used to construct meaningful arithmetic circuit such as quantum adders, the number of ancilla qubits for complicated non-clifford gates and entanglement resources to establish long-distance communication channels, become major performance limiting factors. Next, in order to factorize large integers, these adders are assembled into modular exponentiation circuit comprising bulk of Shor's algorithm. At this stage, the overall scaling of resource-constraint performance with the size of problem, describes the effectiveness of chosen design. By matching the resource investment with the pace of advancement in hardware technology, we find optimal designs for different types of quantum adders. Conclusively, we show that 2,048-bit Shor's algorithm can be reliably executed within the resource budget of 1.5 million qubits.

Jan 1, 20154 citations