Traditional algorithms for simulating quantum computers on classical ones require an exponentially large amount of memory, and so typically cannot simulate general quantum circuits with more than about 30 or so qubits on a typical PC-scale platform with only a few gigabytes of main memory. However, more memory-efficient simulations are possible, requiring only polynomial or even linear space in the size of the quantum circuit being simulated. In this paper, we describe one such technique, which was recently implemented at FSU in the form of a C++ program called SEQCSim, which we releasing publicly. We also discuss the potential benefits of this simulation in quantum computing research and education, and outline some possible directions for further progress.
Traditional algorithms for simulating quantum computers on classical ones require an exponentially large amount of memory, and so typically cannot simulate general quantum circuits with more than about 30 or so qubits on a typical PC-scale platform with only a few gigabytes of main memory. However, more memory-efficient simulations are possible, requiring only polynomial or even linear space in the size of the quantum circuit being simulated. In this paper, we describe one such technique, which was recently implemented at FSU in the form of a C++ program called SEQCSim, which we releasing publicly. We also discuss the potential benefits of this simulation in quantum computing research and education, and outline some possible directions for further progress.
This thesis describes the design and implementation of an environment to allow quantum computation to be simulated on classical computers. Although it is believed that quantum computers cannot in general be efficiently simulated classically, it is nevertheless possible to simulate small but interesting systems, on the order of a few tens of quantum bits. Since the state of the art of physical implementations is less than 10 bits, simulation remains a useful tool for understanding the behavior of quantum algorithms. To create a suitable envrionment for simulation, we constructed a 32-node cluster of workstation class computers linked with a high speed (gigabit Ethernet) network. We then wrote an initial simulation environment based on parallel linear algebra libraries with a Matlab front end. These libraries operated on large matrices representing the problem being simulated. The parallel Matlab environment demonstrated a degree of parallel speedup as we added processors, but overall execution times were high, since the amount of data scaled exponentially with the size of the problem. This increased both the number of operations that had to be performed to compute the simulation, and the volume of data that had to be communicated between the nodes as they were computing. The scaling also affected memory utilization, limiting us to a maximum problem size of 14 qubits. In an attempt to increase simulation efficiency, we revisited the design of the simulation environment. Many quantum algorithms have a structure that can be described using the tensor product operator from linear algebra. We believed that a new simulation environment based on this tensor product structure would be substantially more efficient than one based on large matrices. We designed a new simulation envrionment that exploited this tensor product structure. Benchmarks that we performed on the new simulation environment confirmed that it was substantially more efficient, allowing us to perform simulations of the quantum Fourier transform and the discrete approximation to the solution of 3-SAT by adiabatic evolution up to 25 qubits in a reasonable time. Thesis Supervisor: Stephen A. Benton Title: Professor of Media Arts and Sciences
Quantum computing is based on the exploitation of quantum effects to perform some important computations more efficiently than ever possible on classical computers. Well known quantum algorithms are Shors polynomial time factoring algorithm and Grovers data base search scheme. Their potential is due to the parallelism of a quantum computation increasing exponentially with the size of the computing device. IBM has succeeded in building a first working quantum computing device with up to 7 qubits based on NMR technology, however, the construction of large multi-qubit systems appears to become extremely difficult due to the loss of coherence of the quantum states. Like the design process of modern microprocessors which is carried out by means of sophisticated software, modelling and simulation of the entire QC device is even more relevant. Simulation is required in order to understand the functioning of quantum algorithms, to construct novel quantum algorithms, to write quantum programs, to teach quantum computing, to construct real quantum computers, to understand and fight de-coherence and to understand and control the influence of the environment. Since quantum parallelism increases exponentially with the size of the quantum computer, parallel supercomputers are required for realistic simulations. I intend to give an introduction into the simulation of quantum computers using conventional computers. The simulation is based on a generic physical model of quantum computer hardware. Issues like parallel gate level simulators, modelling of QCs, simulators for physical quantum computers are addressed.
In one-way quantum computation (1WQC) model, universal quantum computations are performed using measurements to designated qubits in a highly entangled state. The choices of bases for these measurements as well as the structure of the entanglements specify a quantum algorithm. As scalable and reliable quantum computers have not been implemented yet, quantum computation simulators are the only widely available tools to design and test quantum algorithms. However, simulating the quantum computations on a standard classical computer in most cases requires exponential memory and time. In this paper, a general direct simulator for 1WQC, called OWQS, is presented. Some techniques such as qubit elimination, pattern reordering and implicit simulation of actions are used to considerably reduce the time and memory needed for the simulations. Moreover, our simulator is adjusted to simulate the measurement patterns with a generalized flow without calculating the measurement probabilities which is called extended one-way quantum computation simulator (EOWQS). Experimental results validate the feasibility of the proposed simulators and that OWQS and EOWQS are faster as compared with the well-known quantum circuit simulators, i.e., QuIDDPro and libquantum for simulating 1WQC model.
Abstract Quantum computing promises advantages for problems in physics, chemistry, and optimization, yet current noisy and small-scale devices limit the implementation of large quantum algorithms. Classical simulation therefore remains essential for algorithm design, verification, and performance benchmarking. However, existing Schrödinger- and Feynman-based simulators suffer from exponential scaling or limited oracle integration. Here we present SparQSim, a C++-based, Feynmaninspired simulator that exploits state sparsity to reduce memory consumption and supports registerlevel operations with integrated quantum random access memory (QRAM). Benchmarks from QASMBench and MQTBench show that for circuits with substantial state space sparsity, which represent the core application scenario of SparQSim, the method surpasses Schrödinger style simulators in both runtime and memory efficiency. Moreover, full-process simulations of quantum linear-system solvers yield results consistent with theoretical predictions. SparQSim provides a flexible and scalable platform for efficient simulation and optimization of quantum algorithms.
Conventional vector-based simulators for quantum computers are quite limited in the size of the quantum circuits they can handle, due to the worst-case exponential growth of even sparse representations of the full quantum state vector as a function of the number of quantum operations applied. However, this exponential-space requirement can be avoided by using general space-time tradeoffs long known to complexity theorists, which can be appropriately optimized for this particular problem in a way that also illustrates some interesting reformulations of quantum mechanics. In this paper, we describe the design and empirical space/time complexity measurements of a working software prototype of a quantum computer simulator that avoids excessive space requirements. Due to its space-efficiency, this design is well-suited to embedding in single-chip environments, permitting especially fast execution that avoids access latencies to main memory. We plan to prototype our design on a standard FPGA development board.
The paper describes the simplest technique for simulating a quantum algorithm based on the direct matrix representation of quantum operators.This approach is stable and precise, but it requires allocation of operator's matrices in the computer memory.Since the size of the operators grows exponentially, this approach is useful for simulating quantum algorithms with a relatively small number of qubits (e.g., approximately 11 qubits on a typical desktop computer).This approach enables relatively simple simulation of the operation of the solution quality control system and performance of a reliability analysis.A more efficient fast quality control simulation method is based on computing all or a part of operator matrices as needed on a current computational basis.This method makes it possible to avoid storing all or a part of the operator matrices.In this case, the number of qubits to be simulated (e.g., the number of input qubits or the number of qubits in the system state register) is affected by: (I) the exponential growth in the number of operations required to calculate the result of matrix products; and (II) the size of the state vector allocated in computer memory.It is reasonable if one embodiment of this approach involves simulating up to 19 or more qubits on typical desktop computer, and even more in a system with a vector architecture.Due to particularities of the memory addressing and access processes in a typical desktop computer (such as, for example, a Pentium PC), when a number of qubits is relatively small, the on-demand computing tends to be faster than the direct storage approach.The compute-on-demand approach benefits from applying the results of studying quantum operators and their structure that enables computing the matrix elements more efficiently.The paper considers effective simulation of Grover's quantum search algorithm using a computer with classical architecture.