The ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer enables the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over Abelian groups, and phase estimation. The standard fault-tolerant implementation of an n-qubit QFT approximates the desired transformation by removing small-angle controlled rotations and synthesizing the remaining ones into Clifford+t gates, incurring the t-count complexity of O(n log2 (n)). In this paper we show how to obtain approximate QFT with the t-count of O(n log(n)). Our approach relies on quantum circuits with measurements and feedforward, and on reusing a special quantum state that induces the phase gradient transformation. We report asymptotic analysis as well as concrete circuits, demonstrating significant advantages in both theory and practice.

UR - https://arxiv.org/abs/1803.04933 ER - TY - JOUR T1 - Toward the first quantum simulation with quantum speedup JF - Proceedings of the National Academy of Sciences Y1 - 2018 A1 - Andrew M. Childs A1 - Dmitri Maslov A1 - Yunseong Nam A1 - Neil J. Ross A1 - Yuan Su AB -With quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, but that requires the fewest resources for a quantum computer. We consider quantum simulation of spin systems, which could be applied to understand condensed matter phenomena. We synthesize explicit circuits for three leading quantum simulation algorithms, using diverse techniques to tighten error bounds and optimize circuit implementations. Quantum signal processing appears to be preferred among algorithms with rigorous performance guarantees, whereas higher-order product formulas prevail if empirical error estimates suffice. Our circuits are orders of magnitude smaller than those for the simplest classically infeasible instances of factoring and quantum chemistry, bringing practical quantum computation closer to reality.

U4 - 201801723 UR - http://www.pnas.org/content/early/2018/09/04/1801723115 U5 - https://doi.org/10.1073/pnas.1801723115 ER - TY - JOUR T1 - Automated optimization of large quantum circuits with continuous parameters Y1 - 2017 A1 - Yunseong Nam A1 - Neil J. Ross A1 - Yuan Su A1 - Andrew M. Childs A1 - Dmitri Maslov AB -We develop and implement automated methods for optimizing quantum circuits of the size and type expected in quantum computations that outperform classical computers. We show how to handle continuous gate parameters and report a collection of fast algorithms capable of optimizing large-scale quantum circuits. For the suite of benchmarks considered, we obtain substantial reductions in gate counts. In particular, we provide better optimization in significantly less time than previous approaches, while making minimal structural changes so as to preserve the basic layout of the underlying quantum algorithms. Our results help bridge the gap between the computations that can be run on existing hardware and those that are expected to outperform classical computers.

UR - https://arxiv.org/abs/1710.07345 ER - TY - JOUR T1 - Basic circuit compilation techniques for an ion-trap quantum machine JF - New Journal of Physics Y1 - 2017 A1 - Dmitri Maslov AB -We study the problem of compilation of quantum algorithms into optimized physical-level circuits executable in a quantum information processing (QIP) experiment based on trapped atomic ions. We report a complete strategy: starting with an algorithm in the form of a quantum computer program, we compile it into a high-level logical circuit that goes through multiple stages of decomposition into progressively lower-level circuits until we reach the physical execution-level specification. We skip the fault-tolerance layer, as it is not necessary in this work. The different stages are structured so as to best assist with the overall optimization while taking into account numerous optimization criteria, including minimizing the number of expensive two-qubit gates, minimizing the number of less expensive single-qubit gates, optimizing the runtime, minimizing the overall circuit error, and optimizing classical control sequences. Our approach allows a trade-off between circuit runtime and quantum error, as well as to accommodate future changes in the optimization criteria that may likely arise as a result of the anticipated improvements in the physical-level control of the experiment.

VL - 19 U4 - 023035 UR - http://iopscience.iop.org/article/10.1088/1367-2630/aa5e47/meta;jsessionid=55CC235A0B106081E825099310586F07.c3.iopscience.cld.iop.org CP - 2 U5 - 10.1088/1367-2630/aa5e47 ER - TY - JOUR T1 - Complete 3-Qubit Grover Search on a Programmable Quantum Computer JF - Nature Communications, accepted Y1 - 2017 A1 - C. Figgatt A1 - Dmitri Maslov A1 - K. A. Landsman A1 - N. M. Linke A1 - S. Debnath A1 - Christopher Monroe AB -Searching large databases is an important problem with broad applications. The Grover search algorithm provides a powerful method for quantum computers to perform searches with a quadratic speedup in the number of required database queries over classical computers. It is an optimal search algorithm for a quantum computer, and has further applications as a subroutine for other quantum algorithms. Searches with two qubits have been demonstrated on a variety of platforms and proposed for others, but larger search spaces have only been demonstrated on a non-scalable NMR system. Here, we report results for a complete three-qubit Grover search algorithm using the scalable quantum computing technology of trapped atomic ions, with better-than-classical performance. The algorithm is performed for all 8 possible single-result oracles and all 28 possible two-result oracles. Two methods of state marking are used for the oracles: a phase-flip method employed by other experimental demonstrations, and a Boolean method requiring an ancilla qubit that is directly equivalent to the state-marking scheme required to perform a classical search. All quantum solutions are shown to outperform their classical counterparts. We also report the first implementation of a Toffoli-4 gate, which is used along with Toffoli-3 gates to construct the algorithms; these gates have process fidelities of 70.5% and 89.6%, respectively.

UR - https://arxiv.org/abs/1703.10535 ER - TY - Generic T1 - Experimental Comparison of Two Quantum Computing Architectures T2 - Proceedings of the National Academy of Sciences Y1 - 2017 A1 - N.M. Linke A1 - Dmitri Maslov A1 - Martin Roetteler A1 - S. Debnath A1 - C. Figgatt A1 - K. A. Landsman A1 - K. Wright A1 - Christopher Monroe AB -We run a selection of algorithms on two state-of-the-art 5-qubit quantum computers that are based on different technology platforms. One is a publicly accessible superconducting transmon device [1] with limited connectivity, and the other is a fully connected trapped-ion system [2]. Even though the two systems have different native quantum interactions, both can be programmed in a way that is blind to the underlying hardware, thus allowing the first comparison of identical quantum algorithms between different physical systems. We show that quantum algorithms and circuits that employ more connectivity clearly benefit from a better connected system of qubits. While the quantum systems here are not yet large enough to eclipse classical computers, this experiment exposes critical factors of scaling quantum computers, such as qubit connectivity and gate expressivity. In addition, the results suggest that co-designing particular quantum applications with the hardware itself will be paramount in successfully using quantum computers in the future.

JA - Proceedings of the National Academy of Sciences VL - 114 U4 - 3305-3310 UR - http://www.pnas.org/content/114/13/3305 U5 - 10.1073/pnas.1618020114 ER - TY - JOUR T1 - Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations Y1 - 2017 A1 - Dmitri Maslov A1 - Martin Roetteler AB -In this paper we improve the layered implementation of arbitrary stabilizer circuits introduced by Aaronson and Gottesman in Phys. Rev. A 70(052328), 2004: to implement a general stabilizer circuit, we reduce their 11-stage computation -HC-P-C-P-C-H-P-C-P-C- over the gate set consisting of Hadamard, Controlled-NOT, and Phase gates, into a 7-stage computation of the form -C-CZ-P-H-P-CZ-C-. We show arguments in support of using -CZ- stages over the -C- stages: not only the use of -CZ- stages allows a shorter layered expression, but -CZ- stages are simpler and appear to be easier to implement compared to the -C- stages. Based on this decomposition, we develop a twoqubit gate depth-(14n−4) implementation of stabilizer circuits over the gate library {H, P, CNOT}, executable in the LNN architecture, improving best previously known depth-25n circuit, also executable in the LNN architecture. Our constructions rely on Bruhat decomposition of the symplectic group and on folding arbitrarily long sequences of the form (-P-C-) m into a 3-stage computation -P-CZ-C-. Our results include the reduction of the 11-stage decomposition -H-C-P-C-P-C-H-P-C-P-C- into a 9-stage decomposition of the form -C-P-C-P-H-C-P-C-P-. This reduction is based on the Bruhat decomposition of the symplectic group. This result also implies a new normal form for stabilizer circuits. We show that a circuit in this normal form is optimal in the number of Hadamard gates used. We also show that the normal form has an asymptotically optimal number of parameters.

UR - https://arxiv.org/abs/1705.09176 ER - TY - JOUR T1 - Toward the first quantum simulation with quantum speedup Y1 - 2017 A1 - Andrew M. Childs A1 - Dmitri Maslov A1 - Yunseong Nam A1 - Neil J. Ross A1 - Yuan Su AB -With quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, but that requires the fewest resources for a quantum computer. We consider quantum simulation of spin systems, which could be applied to understand condensed matter phenomena. We synthesize explicit circuits for three leading quantum simulation algorithms, employing diverse techniques to tighten error bounds and optimize circuit implementations. Quantum signal processing appears to be preferred among algorithms with rigorous performance guarantees, whereas higher-order product formulas prevail if empirical error estimates suffice. Our circuits are orders of magnitude smaller than those for the simplest classically-infeasible instances of factoring and quantum chemistry.

UR - https://arxiv.org/abs/1711.10980 ER - TY - JOUR T1 - Use of global interactions in efficient quantum circuit constructions JF - New Journal of Physics Y1 - 2017 A1 - Dmitri Maslov A1 - Yunseong Nam AB -In this paper we study the ways to use a global entangling operator to efficiently implement circuitry common to a selection of important quantum algorithms. In particular, we focus on the circuits composed with global Ising entangling gates and arbitrary addressable single-qubit gates. We show that under certain circumstances the use of global operations can substantially improve the entangling gate count.

UR - http://iopscience.iop.org/article/10.1088/1367-2630/aaa398 U5 - 10.1088/1367-2630/aaa398 ER - TY - JOUR T1 - On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization JF - Physical Review A Y1 - 2016 A1 - Dmitri Maslov AB - Various implementations of the Toffoli gate up to a relative phase have been known for years. The advantage over regular Toffoli gate is their smaller circuit size. However, their use has been often limited to a demonstration of quantum control in designs such as those where the Toffoli gate is being applied last or otherwise for some specific reasons the relative phase does not matter. It was commonly believed that the relative phase deviations would prevent the relative phase Toffolis from being very helpful in practical large-scale designs. In this paper, we report three circuit identities that provide the means for replacing certain configurations of the multiple control Toffoli gates with their simpler relative phase implementations, up to a selectable unitary on certain qubits, and without changing the overall functionality. We illustrate the advantage via applying those identities to the optimization of the known circuits implementing multiple control Toffoli gates, and report the reductions in the CNOT-count, T-count, as well as the number of ancillae used. We suggest that a further study of the relative phase Toffoli implementations and their use may yield other optimizations. VL - 93 U4 - 022311 UR - http://arxiv.org/abs/1508.03273 CP - 2 U5 - 10.1103/PhysRevA.93.022311 ER - TY - JOUR T1 - Optimal and asymptotically optimal NCT reversible circuits by the gate types JF - Quantum Information & Computation Y1 - 2016 A1 - Dmitri Maslov AB -We report optimal and asymptotically optimal reversible circuits composed of NOT, CNOT, and Toffoli (NCT) gates, keeping the count by the subsets of the gate types used. This study fine tunes the circuit complexity figures for the realization of reversible functions via reversible NCT circuits. An important consequence is a result on the limitation of the use of the T-count quantum circuit metric popular in applications.

VL - 16 U4 - 1096-1112 UR - http://arxiv.org/abs/1602.02627 CP - 13 & 14 ER - TY - JOUR T1 - Practical Approximation of Single-Qubit Unitaries by Single-Qubit Quantum Clifford and T Circuits JF - IEEE Transactions on Computers Y1 - 2016 A1 - Vadym Kliuchnikov A1 - Dmitri Maslov A1 - Michele Mosca AB -We present an algorithm, along with its implementation that finds T-optimal approximations of single-qubit Z-rotations using quantum circuits consisting of Clifford and T gates. Our algorithm is capable of handling errors in approximation down to size 10-15, resulting in the optimal single-qubit circuit designs required for implementation of scalable quantum algorithms. Our implementation along with the experimental results are available in the public domain.

VL - 65 U4 - 161 - 172 UR - http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7056491http://xplorestaging.ieee.org/ielx7/12/7350319/7056491.pdf?arnumber=7056491 CP - 1 J1 - IEEE Trans. Comput. U5 - 10.1109/TC.2015.2409842 ER -