This thesis is about techniques for quantum computing. A common theme throughout this work is the examination of how quantum algorithms and protocols might be implemented in practice. I explore \nthis question at the level of algorithmic details and computer architecture, and not at the level of specific physical systems for \nperforming quantum computation. \n \nThe first problem I consider is the generation of quantum states. Many results in quantum information theory require the generation of specific quantum states, such as Bell states. Some states can be \nefficiently created using standard quantum computational primitives such as preparing a qubit in the state |0> and applying a \nsequence of quantum gates (from a finite set). For example, a Bell state can be prepared from the state |00> using a \nHadamard gate and a controlled-NOT gate. However, many states cannot be efficiently created. Chapter 1 of this thesis focusses on the generation of quantum states. \n \nIn Chapter 2, I explore implementations of Shor's quantum algorithm for computing discrete logarithms. This algorithm \nis particularly significant because it threatens to undermine the security of widely used elliptic curve cryptosystems. I give a strategy for implementing Shor's algorithm for finding discrete logarithms in groups of points on elliptic curves over fields of characteristic 2. \n \nChapter 3 is about globally controlled arrays, which is a paradigm for implementing quantum computers that may prove to be more feasible in practice than the quantum circuit \nmodel. I explore strategies for implementing error correction in such global control models, so that they might be implemented more robustly. I also cast the various global control schemes that have \nappeared in the literature into a unified framework so that their properties can be studied somewhat independently of the differences in low-level details. Using this framework, I consider the main challenges and obstacles to implementing quantum computing fault tolerantly using globally controlled arrays. \n \nFinally, in Chapter 4, I consider algorithmic \ncooling---a technique that is potentially important for making quantum computation using nuclear magnetic resonance (NMR) feasible. Given the constraints imposed by the NMR approach to quantum computing, the most likely cooling algorithms to be practicable are those based on simple reversible polarization (RPC) operations \nacting locally on small numbers of bits. Algorithms using 2- and 3-bit RPC operations have appeared in the literature, and these are the algorithms I consider in Chapter 4. \nSpecifically, I show that the RPC operation used in all these algorithms is essentially a majority-vote of 3 bits, and prove the \noptimality of the best such algorithm (in a restricted setting). I go on to derive some theoretical bounds on the performance of these algorithms under some specific assumptions about errors. These bounds are independent of implementation details and low-level algorithmic details.
This thesis is about techniques for quantum computing. A common theme throughout this work is the examination of how quantum algorithms and protocols might be implemented in practice. I explore \nthis question at the level of algorithmic details and computer architecture, and not at the level of specific physical systems for \nperforming quantum computation. \n \nThe first problem I consider is the generation of quantum states. Many results in quantum information theory require the generation of specific quantum states, such as Bell states. Some states can be \nefficiently created using standard quantum computational primitives such as preparing a qubit in the state |0> and applying a \nsequence of quantum gates (from a finite set). For example, a Bell state can be prepared from the state |00> using a \nHadamard gate and a controlled-NOT gate. However, many states cannot be efficiently created. Chapter 1 of this thesis focusses on the generation of quantum states. \n \nIn Chapter 2, I explore implementations of Shor's quantum algorithm for computing discrete logarithms. This algorithm \nis particularly significant because it threatens to undermine the security of widely used elliptic curve cryptosystems. I give a strategy for implementing Shor's algorithm for finding discrete logarithms in groups of points on elliptic curves over fields of characteristic 2. \n \nChapter 3 is about globally controlled arrays, which is a paradigm for implementing quantum computers that may prove to be more feasible in practice than the quantum circuit \nmodel. I explore strategies for implementing error correction in such global control models, so that they might be implemented more robustly. I also cast the various global control schemes that have \nappeared in the literature into a unified framework so that their properties can be studied somewhat independently of the differences in low-level details. Using this framework, I consider the main challenges and obstacles to implementing quantum computing fault tolerantly using globally controlled arrays. \n \nFinally, in Chapter 4, I consider algorithmic \ncooling---a technique that is potentially important for making quantum computation using nuclear magnetic resonance (NMR) feasible. Given the constraints imposed by the NMR approach to quantum computing, the most likely cooling algorithms to be practicable are those based on simple reversible polarization (RPC) operations \nacting locally on small numbers of bits. Algorithms using 2- and 3-bit RPC operations have appeared in the literature, and these are the algorithms I consider in Chapter 4. \nSpecifically, I show that the RPC operation used in all these algorithms is essentially a majority-vote of 3 bits, and prove the \noptimality of the best such algorithm (in a restricted setting). I go on to derive some theoretical bounds on the performance of these algorithms under some specific assumptions about errors. These bounds are independent of implementation details and low-level algorithmic details.
Shor's quantum algorithm for discrete logarithms applied to elliptic curve groups forms the basis of a ``quantum attack'' of elliptic curve cryptosystems. To implement this algorithm on a quantum computer requires the efficient implementation of the elliptic curve group operation. Such an implementation requires we be able to compute inverses in the underlying field. In \cite{PZ03}, Proos and Zalka show how to implement the extended Euclidean algorithm to compute inverses in the prime field $\GF(p)$. They employ a number of optimizations to achieve a running time of O(n2), and a space-requirement of O(n) qubits, where n is the number of bits in the binary representation of p (there are some trade-offs that they make, sacrificing a few extra qubits to reduce running-time). In practice, elliptic curve cryptosystems often use curves over the binary field $\GF(2^m)$. In this paper, I show how to implement the extended Euclidean algorithm for polynomials to compute inverses in $\GF(2^m)$. Working under the assumption that qubits will be an `expensive' resource in realistic implementations, I optimize specifically to reduce the qubit space requirement, while keeping the running-time polynomial. The implementation here differs from that in $\cite{PZ03}$ for $\GF(p)$, and we are able to take advantage of some properties of the binary field $\GF(2^m)$. I also optimize the overall qubit space requirement for computing the group operation for elliptic curves over $\GF(2^m)$ by decomposing the group operation to make it ``piecewise reversible'' (similar to what is done in \cite{PZ03} for curves over $\GF(p)$).
Quantum computers have the potential to perform computational tasks beyond the reach of classical machines. A prominent example is Shor's algorithm for integer factorization and discrete logarithms, which is of both fundamental importance and practical relevance to cryptography. However, due to the high overhead of quantum error correction, optimized resource estimates for cryptographically relevant instances of Shor's algorithm require millions of physical qubits. Here, by leveraging advances in high-rate quantum error-correcting codes, efficient logical instruction sets, and circuit design, we show that Shor's algorithm can be executed at cryptographically relevant scales with as few as 10,000 reconfigurable atomic qubits. Increasing the number of physical qubits improves time efficiency by enabling greater parallelism; under plausible assumptions, the runtime for discrete logarithms on the P-256 elliptic curve could be just a few days for a system with 26,000 physical qubits, while the runtime for factoring RSA-2048 integers is one to two orders of magnitude longer. Recent neutral-atom experiments have demonstrated universal fault-tolerant operations below the error-correction threshold, computation on arrays of hundreds of qubits, and trapping arrays with more than 6,000 highly coherent qubits. Although substantial engineering challenges remain, our theoretical analysis indicates that an appropriately designed neutral-atom architecture could support quantum computation at cryptographically relevant scales. More broadly, these results highlight the capability of neutral atoms for fault-tolerant quantum computing with wide-ranging scientific and technological applications.
This article surveys the state of the art in quantum computer algorithms, including both black-box and non-black-box results. It is infeasible to detail all the known quantum algorithms, so a representative sample is given. This includes a summary of the early quantum algorithms, a description of the Abelian Hidden Subgroup algorithms (including Shor's factoring and discrete logarithm algorithms), quantum searching and amplitude amplification, quantum algorithms for simulating quantum mechanical systems, several non-trivial generalizations of the Abelian Hidden Subgroup Problem (and related techniques), the quantum walk paradigm for quantum algorithms, the paradigm of adiabatic algorithms, a family of ``topological'' algorithms, and algorithms for quantum tasks which cannot be done by a classical computer, followed by a discussion.
This article surveys the state of the art in quantum computer algorithms, including both black-box and non-black-box results. It is infeasible to detail all the known quantum algorithms, so a representative sample is given. This includes a summary of the early quantum algorithms, a description of the Abelian Hidden Subgroup algorithms (including Shor's factoring and discrete logarithm algorithms), quantum searching and amplitude amplification, quantum algorithms for simulating quantum mechanical systems, several non-trivial generalizations of the Abelian Hidden Subgroup Problem (and related techniques), the quantum walk paradigm for quantum algorithms, the paradigm of adiabatic algorithms, a family of ``topological'' algorithms, and algorithms for quantum tasks which cannot be done by a classical computer, followed by a discussion.
Solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) is critical for evaluating the quantum security of widely deployed elliptic-curve cryptosystems. Consequently, minimizing the number of logical qubits required to execute this algorithm is a key object. In implementations of Shor's algorithm, the space complexity is largely dictated by the modular inversion operation during point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing method of Proos and Zalka and propose a space-efficient reversible modular inversion algorithm. We use length registers together with location-controlled arithmetic to store the intermediate variables in a compact form throughout the computation. We then optimize the stepwise update rules and give concrete circuit constructions for the resulting controlled arithmetic components. This leads to a modular inversion circuit that uses 3n+4⌊log2n⌋+O(1) logical qubits and 204n2log2n+O(n2) Toffoli gates. By inserting this modular inversion component into the controlled affine point-addition circuit, we obtain a space-efficient algorithm for the ECDLP with 5n+4⌊log2n⌋+O(1) qubits and O(n3) Toffoli gates. In particular, for a 256-bit prime-field curve, our estimate reduces the logical-qubit count to 1333, compared with 2124 in the previous low-width implementation of Häner et al.
We show in some detail how to implement Shor's efficient quantum algorithm for discrete logarithms for the particular case of elliptic curve groups. It turns out that for this problem a smaller quantum computer can solve problems further beyond current computing than for integer factorisation. A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits while factoring the security-wise equivalent 1024 bit RSA modulus would require about 2000 qubits. In this paper we only consider elliptic curves over GF(p) and not yet the equally important ones over GF(2^n) or other finite fields. The main technical difficulty is to implement Euclid's gcd algorithm to compute multiplicative inverses modulo p. As the runtime of Euclid's algorithm depends on the input, one difficulty encountered is the ``quantum halting problem''.