International Journal of Modern Physics C

QUANTUM-STATISTICAL SIMULATIONS FOR QUANTUM CIRCUITS

Kurt Fischer, Hans‐Georg Matuttis, Nobuyasu Ito, Masamichi Ishikawa

Published Sep 1, 2002• 2 citations

Abstract

Using a Hubbard–Stratonovich like decomposition technique, we implemented simulations for the quantum circuits of Simon's algorithm for the detection of the periodicity of a function and Shor's algorithm for the factoring of prime numbers on a classical computer. Our approach has the advantage that the dimension of the problem does not grow exponentially with the number of qubits.

DOI: 10.1142/s012918310200367x

Related papers

AUXILIARY FIELD METHODS FOR THE SIMULATION OF QUANTUM COMPUTATION CIRCUITS

Hans‐Georg Matuttis, Kurt Fischer, Nobuyasu Ito +1 more

One obstacle in the simulation of quantum circuits is the high dimension of the Hilbert space. Using auxiliary field decompositions known from many-particle simulation, we can transform the mathematical description of the quantum circuit into a combination low-dimensional product states which can be sampled using Monte Carlo techniques. We demonstrate the method using Simon's algorithm for the detection of the period of a function.

International Journal of Modern Physics CSep 1, 20021 citation

A Key Component of the Shor's Algorithm and Its Possible Quantum Implementations

Jiří Tomčala

A fundamental problem in factorization by Shor's algorithm [1] is the implementation of the modular exponentiation function. The period of this function is important for determining the individual factors, so its accurate implementation is for successful factorization critical.The imprecision of current quantum computers requires that any quantum circuits should be as simple as possible. Both in terms of the number of qubits used, the number of quantum gates and the depth of the quantum circuit. Therefore, it is necessary to search for an optimal variant for the implementation of the above-mentioned modular exponentiation function.The standard method is to implement individual arithmetic functions [2] which can be combined to achieve the desired modular exponentiation function. This process, however, creates a very complex quantum circuit, so that its measured result (probability distribution) will be so skewed that it will not be possible to reliably obtain the period of sought.Another way is to create a special quantum circuit for one particular modular exponentiation function [3]. Such a circuit is of course simpler than the circuit created by the above universal implementation, but in practice it only makes sense for testing the functionality of the surrounding quantum circuit for period detection.A very interesting possibility for the implementation of arithmetic functions is to use the direct and inverse quantum Fourier transform [4]. For a quantum computer, these transformations are very easy operations, and this interesting feature can then be used to advantage in these various implementations.This contribution will explore these possible approaches and show their advantages and disadvantages through concrete examples.

Dec 17, 20250 citations

Simulation of a Quantum Prime Factoring Algorithm

Elizabeth Ellen Parsons

The intent of this thesis is to elucidate the quantum computing algorithm developed by Peter Shor called Shor's algorithm. We will provide a detailed description and simulation of the algorithm using MATLAB. Precursory information regarding quantum phenomena such as superposition, entanglement, and Dirac notation, will be described in great detail so that the reader may have a better understanding of the operations in Shor's algorithm. Quantum computers store and transport information quite differently than their classical counterparts. We will provide a quick overview of these differences to high- light the benefit of utilizing quantum phenomena in a computer in order to create massive parallel computations. Thus, reducing the complexity time for classical algorithms used to solve problems such as the prime factorization problem and the period finding problem. The Quantum Fourier Transform is a principle component in Shor's algorithm. We will explicitly define the Quantum Fourier Transform and show that it is a unitary transformation. We will also show how the Quantum Fourier Transform, as well as another unitary transformation called the Hadamard transform, functions in Shor's algorithm. One of the initial parameters in Shor's algorithm is to select a random variable. We will examine the erratic effects of this random variable as well as how it effects the probability of us successfully reducing an integer into a product of two primes. We will provide a thorough analysis of the randomness in Shor's algorithm. We will also show how measuring the state of our quantum system as well as selecting a suitable random variable impacts finding the period of the Quantum Fourier Transform which in turn will either give a high or low probability of obtaining a factor of some integer.

Jan 1, 20160 citations

Shor's factorization algorithm

E. Desurvire

This chapter describes what is generally considered to be one of the most important and historical contributions to the field of quantum computing, namely Shor's factorization algorithm . As its name indicates, this algorithm makes it possible to factorize numbers, which consists in their decomposition into a unique product of prime numbers. Other classical factorization algorithms previously developed have a complexity or computing time that increases exponentially with the number size, making the task intractable if not hopeless for large numbers. In contrast, Shor's algorithm is able to factor a number of any size in polynomial time , making the factorization problem tractable should a quantum computer ever be realized in the future. Since Shor's algorithm is based on several nonintuitive properties and other mathematical subtleties, this chapter presents a certain level of difficulty. With the previous chapters and tools readily assimilated, and some patience in going through the different preliminary steps required, such a difficulty is, however, quite surmountable. I have sought to make this description of Shor's algorithm as mathematically complete as possible and crack-free, while avoiding some academic considerations that may not be deemed necessary from any engineering perspective. Eventually, Shor's algorithm is described in only a few basic instructions. What is conceptually challenging is to grasp why it works so well, and also to feel comfortable with the fact that its implementation actually takes a fair amount of trial and error. The two preliminaries of Shor's algorithm are the phase estimation and the related order-finding algorithms.

Cambridge University Press eBooksFeb 19, 20090 citations

Implementation of the Shor Algorithm on a Quantum Circuit

Alexei Petrenko, Sergei Petrenko

This chapter analyzes the applicability of Fourier transformations to determine the periodic structure of finite-length sequences. The classical factorization problem is reformulated to solve it on modern quantum computers with 16 or more qubits. The chapter presents Shor's algorithm for factorization of natural numbers. Performing two basic quantum operations is required to implement the described Shor algorithm, namely exponentiation and quantum discrete Fourier transformation. The chapter estimates the amount of quantum resources needed to solve some asymmetric cryptographic problems using derivatives of the Shor algorithm, with different parameters of these problems, and compares them with the complexity of solving the iterative problem when searching for the key of a symmetric cryptosystem. Using the example of solving the problem of finding the exponent (multiplicative order) of a simple integer modulo by another simple integer, the chapter shows the main features of modeling and engineering implementation of the quantum Shor algorithm.

River Publishers eBooksFeb 7, 20230 citations

Shor Factoring Algorithm and the Quantum Fourier Transform

Alice Flarend, Robert Hilborn

Abstract Expanding on the factoring and periodicity in Chapter 14, the Shor algorithm is explained in detail, with a warning that this is one of the toughest chapters in the book. While the steps of Shor algorithm may look just like the RSA in reverse, the quantum computer is needed to find the periodicity of the factors and thereby the prime factors themselves. Fourier analysis is the tool for this. The quantum Fourier transform is described, including the quantum circuit, after first showing what the classical Fourier transform accomplishes. Extensive examples of all the steps are given.

Jul 9, 20260 citations