Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userArchitecture of a Quantum Multicomputer Optimized for Shors Factoring Algorithm
160
0
0.0
(
0
)
Authors
Rodney Doyle Van Meter III
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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 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 present a novel and efficient in terms of circuit depth design for Shors quantum factorization algorithm. The circuit effectively utilizes a diverse set of adders based on the quantum Fourier transform (QFT) Drapers adders to build more complex arithmetic blocks: quantum multiplier/accumulators by constants and quantum dividers by constants. These arithmetic blocks are effectively architected into a generic modular quantum multiplier which is the fundamental block for modular exponentiation circuit, the most computational intensive part of Shors algorithm. The proposed modular exponentiation circuit has a depth of about $2000n^{2}$ and requires $9n+2$ qubits, where $n$ is the number of bits of the classical number to be factored. The total quantum cost of the proposed design is $1600n^{3}$. The circuit depth can be further decreased by more than three times if the approximate QFT implementation of each adder unit is exploited.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
