Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFactoring with Qutrits: Shors Algorithm on Ternary and Metaplectic Quantum Architectures
76
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We determine the cost of performing Shors algorithm for integer factorization on a ternary quantum computer, using two natural models of universal fault-tolerant computing: (i) a model based on magic state distillation that assumes the availability of the ternary Clifford gates, projective measurements, classical control as its natural instrumentation set; (ii) a model based on a metaplectic topological quantum computer (MTQC). A natural choice to implement Shors algorithm on a ternary quantum computer is to translate the entire arithmetic into a ternary form. However, it is also possible to emulate the standard binary version of the algorithm by encoding each qubit in a three-level system. We compare the two approaches and analyze the complexity of implementing Shors period finding function in the two models. We also highlight the fact that the cost of achieving universality through magic states in MTQC architecture is asymptotically lower than in generic ternary case.
rate research
Read More
We report a proof-of-concept demonstration of a quantum order-finding algorithm for factoring the integer 21. Our demonstration involves the use of a compiled version of the quantum phase estimation routine, and builds upon a previous demonstration by Martin-L{o}pez et al. in Nature Photonics 6, 773 (2012). We go beyond this work by using a configuration of approximate Toffoli gates with residual phase shifts, which preserves the functional correctness and allows us to achieve a complete factoring of N=21. We implemented the algorithm on IBM quantum processors using only 5 qubits and successfully verified the presence of entanglement between the control and work register qubits, which is a necessary condition for the algorithms speedup in general. The techniques we employ may be useful in carrying out Shors algorithm for larger integers, or other algorithms in systems with a limited number of noisy qubits.
The quantum multicomputer consists of a large number of small nodes and a qubus interconnect for creating entangled state between the nodes. The primary metric chosen is the performance of such a system on Shors algorithm for factoring large numbers: specifically, the quantum modular exponentiation step that is the computational bottleneck. This dissertation introduces a number of optimizations for the modular exponentiation. My algorithms reduce the latency, or circuit depth, to complete the modular exponentiation of an n-bit number from O(n^3) to O(n log^2 n) or O(n^2 log n), depending on architecture. Calculations show that these algorithms are one million times and thirteen thousand times faster, when factoring a 6,000-bit number, depending on architecture. Extending to the quantum multicomputer, five different qubus interconnect topologies are considered, and two forms of carry-ripple adder are found to be the fastest for a wide range of performance parameters. The links in the quantum multicomputer are serial; parallel links would provide only very modest improvements in system reliability and performance. Two levels of the Steane [[23,1,7]] error correction code will adequately protect our data for factoring a 1,024-bit number even when the qubit teleportation failure rate is one percent.
We study the results of a compiled version of Shors factoring algorithm on the ibmqx5 superconducting chip, for the particular case of $N=15$, $21$ and $35$. The semi-classical quantum Fourier transform is used to implement the algorithm with only a small number of physical qubits and the circuits are designed to reduce the number of gates to the minimum. We use the square of the statistical overlap to give a quantitative measure of the similarity between the experimentally obtained distribution of phases and the predicted theoretical distribution one for different values of the period. This allows us to assign a period to the experimental data without the use of the continued fraction algorithm. A quantitative estimate of the error in our assignment of the period is then given by the overlap coefficient.
The number of steps any classical computer requires in order to find the prime factors of an $l$-digit integer $N$ increases exponentially with $l$, at least using algorithms known at present. Factoring large integers is therefore conjectured to be intractable classically, an observation underlying the security of widely used cryptographic codes. Quantum computers, however, could factor integers in only polynomial time, using Shors quantum factoring algorithm. Although important for the study of quantum computers, experimental demonstration of this algorithm has proved elusive. Here we report an implementation of the simplest instance of Shors algorithm: factorization of ${N=15}$ (whose prime factors are 3 and 5). We use seven spin-1/2 nuclei in a molecule as quantum bits, which can be manipulated with room temperature liquid state nuclear magnetic resonance techniques. This method of using nuclei to store quantum information is in principle scalable to many quantum bit systems, but such scalability is not implied by the present work. The significance of our work lies in the demonstration of experimental and theoretical techniques for precise control and modelling of complex quantum computers. In particular, we present a simple, parameter-free but predictive model of decoherence effects in our system.
We optimize the area and latency of Shors factoring while simultaneously improving fault tolerance through: (1) balancing the use of ancilla generators, (2) aggressive optimization of error correction, and (3) tuning the core adder circuits. Our custom CAD flow produces detailed layouts of the physical components and utilizes simulation to analyze circuits in terms of area, latency, and success probability. We introduce a metric, called ADCR, which is the probabilistic equivalent of the classic Area-Delay product. Our error correction optimization can reduce ADCR by an order of magnitude or more. Contrary to conventional wisdom, we show that the area of an optimized quantum circuit is not dominated exclusively by error correction. Further, our adder evaluation shows that quantum carry-lookahead adders (QCLA) beat ripple-carry adders in ADCR, despite being larger and more complex. We conclude with what we believe is one of most accurate estimates of the area and latency required for 1024-bit Shors factorization: 7659 mm$^{2}$ for the smallest circuit and $6 * 10^8$ seconds for the fastest circuit.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
