Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Re-evaluation of Shors Algorithm
49
0
0.0
(
0
)
Authors
John W. Cooper
Ask ChatGPT about the research
No Arabic abstract
Shors algorithm is examined critically from the standpoint of its eventual use to obtain the factors of large integers.
rate research
Read More
We show how the execution time of algorithms on quantum computers depends on the architecture of the quantum computer, the choice of algorithms (including subroutines such as arithmetic), and the ``clock speed of the quantum computer. The primary architectural features of interest are the ability to execute multiple gates concurrently, the number of application-level qubits available, and the interconnection network of qubits. We analyze Shors algorithm for factoring large numbers in this context. Our results show that, if arbitrary interconnection of qubits is possible, a machine with an application-level clock speed of as low as one-third of a (possibly encoded) gate per second could factor a 576-bit number in under one month, potentially outperforming a large network of classical computers. For nearest-neighbor-only architectures, a clock speed of around twenty-seven gates per second is required.
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.
Simulating quantum systems constructively furthers our understanding of qualitative and quantitative features which may be analytically intractable. In this letter, we directly simulate and explore the entanglement structure present in a paradigmatic example of quantum information: Shors wavefunction. The methodology employed is a dynamical tensor network which is initially constructed as a tree tensor network, inspired by the modular exponentiation quantum circuit, and later efficiently mapped to a matrix product state. Utilizing the Schmidt number as a local entanglement metric, our construction explicitly captures the wavefunctions non-local entanglement structure and an entanglement scaling relation is discovered. Specifically, we see that entanglement across a bipartition grows exponentially in the number of qubits before saturating at a critical scale which is proportional to the modular periodicity.
Shors powerful quantum algorithm for factoring represents a major challenge in quantum computation and its full realization will have a large impact on modern cryptography. Here we implement a compiled version of Shors algorithm in a photonic system using single photons and employing the non-linearity induced by measurement. For the first time we demonstrate the core processes, coherent control, and resultant entangled states that are required in a full-scale implementation of Shors algorithm. Demonstration of these processes is a necessary step on the path towards a full implementation of Shors algorithm and scalable quantum computing. Our results highlight that the performance of a quantum algorithm is not the same as performance of the underlying quantum circuit, and stress the importance of developing techniques for characterising quantum algorithms.
We detail techniques to optimise high-level classical simulations of Shors quantum factoring algorithm. Chief among these is to examine the entangling properties of the circuit and to effectively map it across the one-dimensional structure of a matrix product state. Compared to previous approaches whose space requirements depend on $r$, the solution to the underlying order-finding problem of Shors algorithm, our approach depends on its factors. We performed a matrix product state simulation of a 60-qubit instance of Shors algorithm that would otherwise be infeasible to complete without an optimised entanglement mapping.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
