Efficient Quantum Circuit Simulation PDF Download

Quantum computers promise to extend the domain of the computable, performing calculations thought to be intractable on any classical device. Rapid experimental and technological progress suggests that this promise could soon be realized. However, these first quantum computers will inevitably be both small, faulty, and expensive, demanding implementations of quantum algorithms which are compact, fast, and error-resistant. As the complexity of realizable quantum computers accelerates toward the threshold of quantum supremacy, their capacity to demonstrate a meaningful quantum advantage when applied to real-world tasks depends on the high-performance design, implementation, and analysis of quantum circuits. The first half of the thesis is devoted to Shor's factoring algorithm, seeking to determine the most efficient quantum circuit implementation of a quantum modular multiplier. Three such implementations are introduced which outperform the best known exact reversible modular multiplier circuits for most practical problem sizes. Reformulated in the framework of quantum Fourier transform (QFT) based arithmetic, two of these circuits are further shown to reduce modular multiplication to a constant number of QFT-like circuits, which can then parallelized to a linear-depth circuit with just 2n + O(log n) qubits. Motivated by this deconstruction, the final result in this portion is an algorithm for a 'SIMD QFT' - demonstrating that the parallel QFT can be efficiently implemented on a topologically-limited distributed ion-trap architecture with just a single global shuttling instruction. The second half of this thesis focuses on quantum signal processing (QSP), specifically as applied to quantum Hamiltonian simulation. Hamiltonian simulation promises to be one of the first practical applications for which a near-term device could demonstrate an advantage over all classical systems. We use high-performance classical tools to construct, optimize, and simulate quantum circuits subject to realistic error models in order to empirically determine the maximum tolerable error rate for a meaningful Hamiltonian simulation experiment on a near-term quantum computer. By exploiting symmetry inherent to the QSP circuit, we demonstrate that their capacity for quantum simulation can be increased by at least two orders of magnitude if errors are systematic and unitary. This portion concludes with a thorough description of the classical simulation software used for the this analysis..