Reach Us
+32-10-28-02-25

**Sowa A ^{*}**

Department of Mathematics and Statistics, University of Saskatchewan, Canada.

- *Corresponding Author:
- Sowa A

Professor

Department of Mathematics and Statistics

University of Saskatchewan, Canada

**Tel:**154445354154

**E-mail:**[email protected]

**Received Date:** April 08, 2016; **Accepted Date:** June 22, 2016; **Published Date:** June 27, 2016

**Citation: **Sowa A (2016) The Quantum Sieve of Eratosthenes. J Phys Math 7:180. doi:10.4172/2090-0902.1000180

**Copyright:** © 2016 Sowa A. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

**Visit for more related articles at** Journal of Physical Mathematics

We introduce and examine quantum states of a special kind, referred to as E-states, whose properties are both structurally and functionally analogous to the sieve of Eratosthenes. More broadly, the concept of an E-state is related to a certain noncommutative extension of the Dirichlet ring, also discussed here for the first time. Furthermore, we demonstrate that E-states can be implemented on a universal quantum computer and, as a particular application, we construct an algorithm which implements the Dirichlet multiplication of sequences on a quantum computer. We also discuss the potential applicability of E-states to the problem of integer factorization although, we haste to add, we are not aware at present of the possibility of using this approach to obtain algorithms of sub-exponential complexity

Quantum sieve; Quantum algorithm for Dirichlet multiplication (convolution); Integer factorization

Quantum parallelism is a phenomenon that Nature herself seems to be suggesting as a means to getting around repetitive chores of forbidding duration. It is the cornerstone of most if not all interesting quantum computing schemas and the main factor responsible for computational speedups of some quantum algorithms, e.g. Shor’s pioneering integer factorization algorithm, [1]. Arguably, quantum parallelism may be so distinct a feature of quantum algorithms that the efficiency some of them provide will remain unachievable within the Church-Turing’ian model of computation [2,3].

In this article we explore possible advantages of some quantum structures deemed analogous to the classical sieve of Eratosthenes. The main idea is to set a bipartite quantum system in a state of the form Σ*a*_{lk}|l⟩ k⟩ with amplitudes *a*_{lk} nonzero only if *k*|*l* (i.e. *l* can be divided by *k* without remainder). We refer to such states as Eratosthenian states or, simply, E-states. If we were skilled in the art of creating E-states with good control they could be used for efficient integer factorization. Suppose we wanted to find a divisor *K* of *N*, where *N* is a number with *n*~log *N* bits (in binary representation). All we would have to do is implement an E-stare with only a polynomial in n quantity of comparable-magnitude amplitudes *a*_{lk}≠0, including *a _{Nk}* ≠0. If such a state were created we would be able to find the factor

It is one of the conclusions reached in this paper that the algebra of the Dirichlet polynomials — i.e. objects of the type , where the sum is finite — may be handled by a quantum computer. This extends our earlier work in which we demonstrated that the Dirichlet polynomials may be efficiently manipulated on a classical computer. In both cases the manipulation of Dirichlet polynomials is enabled by their matrix representation (which also extends to the infinite Dirichlet series). This fact has numerous practical applications [4-6].

**E-matrices**

Consider a matrix A=[*a _{nk}*], and either

When written explicitly an E-matrix assumes the form

where the entries represented by centred dots are necessarily zeros, and only if *k*|*n* the entry *a _{nk}* may be nonzero. If an

It is demonstrated in Subsection 2.2 that every *ε _{N}N*∈{2,3,4…}∪{∞}, is a ring with respect to the regular matrix addition and multiplication. We also point out that every

Therefore, ε_{∞} furnishes a noncommutative extension of the Dirichlet ring.

**E-matrices form a noncommutative ring**

Readers who are interested only in the quantum-computing applications of E-matrices may skip this subsection.

**Theorem 2.1:** *Let N∈{2,3,4…}∪{∞}.N is a ring with respect to the operations of matrix addition and multiplication. The ring has a unity given by the identity matrix I. For A,B∈ε _{N}, AB=I if and only if BA=I. Moreover,A∈ε_{N} has an inverse (in ε_{N}) if and only if all the diagonal entries of A are nonzero.*

**Proof:** *It is ion. Next, we verify that the product of two E matrices is an E-matrix. Indeed, for A,B∈ε _{N}, let[c_{nk}]=C=obvious that ε_{N} is a group with respect to matrix addition. Furthermore, the identity matrix clearly is the unit of multiplicatAB. We have*

(Here,*k*|*d*|*n* is used as shorthand for: *k*|*d* & *d*|*n*.) Thus, for the righthand side sum to be nonzero at least one of the terms must be nonzero, which implies k|n, i.e. *C* is an *E*-matrix.

It follows from (3) that if *A,Bε _{N}* and

Where δ* _{nk}*∈{0,1} is the Kronecker delta. This determines the diagonal entries of

Note that (5) determines *b _{nk}* via

It follows that *C _{nn}*=1/

This gives recurrence for *c _{nk}* if the indices are suitably ordered. Namely, if

**Corollary 2.1:** *The ring, ε _{N}*N∈{2,3,4…}∪{∞},

Proof: In light of Theorem 2.1 we see that the set of non-invertible elements in ε_{N} (N>2) or ε_{∞} is not additively closed. Indeed, the sum of two *E* matrices each with some zeros on the diagonal can yield a matrix whose all diagonal entries are all nonzero. The claim then follows from Theorem 7.1.1 in [8].

**Remark 1:** Note that the set of all matrices in ε_{N} (or ε_{∞}) with a zero column (resp. zero row) is a left (resp. right) ideal. The fact that a ring is not local means that the set of non-invertible elements is not a twosided ideal. Moreover, neither of the rings has a largest proper left or right ideal, [8].

Remark 2: Note that the recurrence formulas (5) or (7) yield the inverse matrix by filling up consecutively increasing blocks. This can be viewed alternatively in the following way. A matrix *A*∈ε_{N} has a block structure as follows:

Suppose det , and let us look for *A*^{-1} in the form,

In such a case *A*^{-1}*A=I* is equivalent to the following set of constraints:

Let *X*=[*x _{1}*,…

**Quantum E-states**

Consider a pair of quantum systems which, when in isolation, have the dynamics determined by the Hamiltonians

*H _{i}* : → (

Suppose the composite system is initialized in the state,

Where *E*=[*a _{nk}*] is an E-matrix with the Hilbert-Schmidt norm The Schrödinger dynamics with the initial condition amounts to a separable evolution of the coefficients and so , where. This means that if |Ψ(

**Quantum measurements and integer factorization**

Suppose an E-state |Ψ(*E*)⟩ has been prepared in such a way that *a _{nk}*≠0 ⇒

**E-states on a quantum computer**

In this section we consider two different approaches to the construction of an E-state on a quantum computer. The first method relies upon the quantum multiplication circuit, while the second utilizes a quantum gate implementation of a specific arithmetic function. In both cases the resulting state is a superposition of a pure E-state with some additional “artefact" state components. However, as explained below, the pure E-state components are separated from the artefact components by their index range. Thus pure components can be separated a posteriori by a rudimentary classical observation or, alternatively, enhanced via the procedure known as amplitude amplification, [9].

The departure point for both constructions is the known process for creating an equal superposition state, see e.g. [10]. This is obtained by an application of the single qubit Hadamard gates to the ground state:

**An E-state from quantum multiplication**

We will demonstrate how to prepare an E-state on a quantum computer with a quantum random access memory consisting of two registers. We let |*x*⟩ |*y* denote the state of the registers, where it is understood that |*x*⟩=|*x*_{1},*x*_{2},*x*_{3},..*x _{n}*⟩ is an n-qubit representation and, similarly, |

Where *x*.*y* denotes the product of two integers. (Here, multiplication may be effectively replaced by multiplication mod 2^{2n}.) However, since multiplication by zeros is not interesting we introduce a modification. Namely, we first add 1 to both *x* and *y*, effectively using

Note that is unitary, and implementable as simplified addition, as long as the register is by one qubit larger that the maximal value of x. Similarly, unitarity implies that |*x*+1⟩|(*x*+1)(*y*+1)⟩ cannot fall off the register range. Therefore, the second register should have at least M=2^{2n} qubits. We will now combine (11) with (12) to create an *E*-state. Indeed, in step one we set both registers in the equal superposition states:

The output state is very similar to an E-state except for some artefacts. The artefacts can be effectively dealt with either by treating them as a tolerable nuisance, and doing nothing until the quantum information is accessed, or else countermanding them via an application of the Grover’s search (amplitude amplification). We illustrate the procedure by an example with *n*=2, and M=*n*^{2}=4. Note that the first register must support *n*+1=3 qubits. The end state in this case has the form (here *c*=1/4):

Note that not shown are rows corresponding to the states |5⟩,|6⟩,|7⟩ or |0⟩ on the first register—these rows contain only zero entries. Furthermore, note that the submatrix corresponding to values |1⟩,|2⟩,|3⟩,|4⟩ on the second register is the transpose of an *E*-matrix^{3}. We also note that a measurement on both registers returns a pair of integers (*a*,*b*) where, *a*|*b*. (In the example at hand the special pair (4,0) signifies (4,16) .Note that those components of the output state that correspond to values other than |1⟩,|2⟩,|3,|4⟩ on the second register cannot be erased, because such an operation would not be unitary. However, the resulting state contains an E-state as a separable component. Summarizing, the proposed algorithm for the creation of an approximate E-state consists of the following steps:

• Prepare an initial state according to (11).

• Compute the (shifted) quantum product according to (13). As a result obtain an output state |Ψ_{out}⟩=|Ψ_{E}⟩+|Ψ_{R}⟩, where |Ψ_{E}⟩ is (proportional to) an E-state and |Ψ_{R}⟩ is a remainder.

• Separate |Ψ_{E}⟩ classically in the following sense: the measurement outcomes that belong in an E-state component are precisely those |*x*⟩|*z*⟩ where z∈{1,2…2^{n}}

• Optionally, depending on an application, it may be beneficial to engage the generalized Grover’s search as a processing step preceding the classical separation. This step provides amplitude amplification, effectively boosting the weight of the |Ψ_{E}⟩ component and suppressing that of the |Ψ_{E}⟩.

**Remark 1:** Note that the probability of an outcome that is an E-state component is (*d*(1) + *d*(2) +*d*(2^{n} )) / 2^{2n}~2^{n} log 2^{n} /2^{2n}~*n* / 2^{n} . However, measurements on the full output state provide useful information, and separation of the E-state pointed out in the last step of the algorithm need not always be desirable. We emphasize that the probability of obtaining from measurement any pair a|b is always the same and equal to 2^{-2n}.

**Remark 2:** The network complexity for multiplication of two registers is of the order *n*^{2}. There are several known circuit architectures implementing multiplication. While some implementations rely on the quantum Fourier transform, [12], the classical Vedral-Barenko- Ekert algorithm does not use it, [11]. Even though the latter algorithm demands a greater memory resource, it seems to secure computational stability independent of the input size.

**Remark 3:** Recall that the Grover search, as well as its various generalizations known as the *amplitude amplification algorithms*, [9], rely on the Grover rotation. To briefly summarize the principle and compute the complexity, we turn attention to |Ψ_{out}⟩=|Ψ_{E}⟩+|Ψ_{R}⟩. The quantities *a*=⟨_{E}|Ψ_{E}⟩ and *b*=⟨Ψ_{R}|Ψ_{R}⟩ represent the probabilities of measuring a good component, in the support of |Ψ_{E}⟩, and a bad component in the support of |Ψ_{R}. We wish to apply a quantum circuit to |Ψ_{out}⟩ so as to boost the probability of measuring the good component. To this end we use the Grover’s rotation:

Grover’s rotation is applied *k* times to |Ψ_{out}⟩ so that *G ^{k}* |Ψ

i.e. the number of iterations is essentially exponential in *n*.

**An E-state from** *f*(*x*)=[*N*/*x*]. *x*.

This method is based on a quantum implementation of the arithmetic function *f*(*x*)=[*N*/*x*]. *x*, *x*∈N. (We will not discuss the specific circuit implementation of this function, all reversible classical functions can be converted into quantum computations [13]. We wish to construct an E-state concentrated near the N’th column, where N<2^{n}. To this end we prepare the state on the first register and subsequently implement a two-register operation.

The result is a relatively sparse E-state in superposition with an artefact vector. Let us illustrate this with an example for *N*=6. Selecting *n*=3, we obtain the following state matrix ( *c* =1/ ):

Note that the first register requires 4 qubits, and only part of it is shown. The E-state submatrix is indexed by |1⟩……|6 on both registers. As before there is some overflow of energy to artefact state components, in this case, *c*|7⟩|0⟩+c|8⟩|0⟩. As before the artefact components can be separated classically a posteriori or suppressed via amplitude amplification.[13]

Note that in general a measurement will result in drawing a nontrivial divisor of N with probability 2^{-n}(*d*(*N*)-2). Again, one may apply the Grover’s rotation in order to bring the state close to the state supported on the *d*(*N*)-2 good components, which requires iterations.

**Applying the quantum Fourier transform**

Let us briefly examine the effect of an application of the quantum Fourier transform (QFT) to an E-state. In the next subsection we will discuss the topic from a more general point of view, but it is helpful to first focus on the E-state part of |Ψ_{out}⟩=|Ψ_{E}⟩+|Ψ_{R}⟩ as in (13). As remarked above, |_{E}⟩ is separated from the remainder |Ψ_{R}⟩ by the second register range 1≤*z*≤2^{n}. We will refer to the |Ψ_{R}⟩ term as ‘out of bounds’ (OOB). Thus,

Where δ_{.|z}(*x*)=1 if *x* |*z* and δ_{.|z}(*x*)=0 otherwise. Recall, [9], that the *n*-qubit QFT is defined via

Applying the shift on the first register, and setting *f _{z}*(

where for all *z * is the discrete Fourier transform of fz. It is interesting to observe that = 2^{-n/2}*d*(*z*). Therefore, if the output state has been prepared as this, then from among the output states of the form |0⟩|*z*⟩, the more highly composite numbers, i.e. those with larger d(z), are more likely to be measured. [*β*_{1}, *β*_{2}..]^{T} =A[α_{1}, α_{2},…]^{T}

**The Dirichlet product of state vectors**

In recent years there has been a trend in quantum computing to go beyond the realm of discrete algorithms and consider the possibility of manipulating the vectors represented in quantum state amplitudes. A representative example of that trend is reference [14], wherein the authors address the problem of solving on a quantum computer the linear equation [*β*_{1}, *β*_{2}..]^{T} =A[α_{1}, α_{2},…]^{T}. Here |α⟩=Σαx|x⟩ is regarded as given, A is a classically known matrix, and

|*β*⟩=Σ *β _{x}*|

Where is a probability distribution^{4} on {1,2,…2^{n}} With this understood, we will now show how to use the concepts introduced in the preceding paragraphs to describe an implementation of new types of E-states as well as the realization of the Dirichlet multiplication of the amplitude vectors. First, consider a straightforward generalization of (13). Namely,

Let us examine an example, assuming *n*=2, and *M*=*n*^{2}=4 (*M*=4 is the number of qubits required for the second register, and *n*+1=3 is the number of qubits required for the first register.) In such a case |Ψ_{out}⟩ assumes the form:

Note that the 4-by-4 submatrix delineated by the vertical lines supports an E-state component. In general, we have

This is much more general an E-state than that obtained in (13).

Next, we perform further computation of the output state. We first shift on the first register, and then follow by the QFT on the first register. In detail, by letting *f _{z}*=δ

Finally, we observe

Where α⋆*β* is the Dirichlet product (convolution) of the sequences α and β Thus, the component of |_{out}⟩ distinguished by |0⟩ on the first register is

Note that the example considered in subsection 3.3 is a special case and returns *d*(*z*)=*ee*(*z*), where *e*=[1,1,1,..]

Summarizing, the amplitudes at G^{k} |Ψ_{out}⟩ at |0|*z*⟩ components hold information about α⋆*β*(*z*). This type of information can only be accessed statistically. We point out yet again that the amplitude amplification via the Grover’s search algorithm may be engaged to obtain G^{k} |Ψ_{out}⟩~|Ψ_{D}⟩. The number of iterations is

**Remark:** We recall that the known QFT algorithm has Θ(*n*^{2}) complexity. Of course, since the QFT depends on unitary transforms with terms like exp 2π /2^{n} its hardware implementation requires precision (in terns of energy control or ultra-short pulse control, etc.) that is exponential in *n*. Notably, however, in some applications this difficulty may be overcome by replacing the QFT with the *approximate quantum Fourier transform* (AQFT) introduced in [16]. It is interesting to enquire whether the AQFT might facilitate additional gains also in the task of integer factorization via E-states. However, we do not undertake to address this problem here.

As explained in Section 2.3 once an E-state of the form (10) is formed, it will be preserved essentially unchanged in time (except for the unessential phase factors) as long as no measurement is conducted on the composite system. In this section we consider the problem of forming such a state outside the framework of the universal quantum computer. Indeed, one might hope that abandoning the constraint of universality would open more options for achieving such a goal. The approach we consider is based on the thermodynamic equilibrium, and utilizes the results for another application of those results. [17,18]

For simplicity we henceforth assume that |Ψ_{E}⟩ is effectively finite. The first observation is that an E-state may be reduced to a more standard state via the Schmidt representation. Indeed, let *E=USV* be the SVD decomposition of the matrix *E*=[*a _{nk}*] that holds the amplitudes of |Ψ

We will use these observations to attempt a construction of a quantum system regime in which |Ψ_{E}⟩ will become its stationary state. The basic concept of adiabatic computing is to switch from the regime that instils |Ψ_{E}⟩ back to the dynamics governed by the Hamiltonian (9) not disturbing the system state. To this end, one might try to construct an isolated system Hamiltonian for which (17) is a ground state. However, we propose an alternative approach, based on thermodynamic equilibrium at constant temperature. First, we define a Hamiltonian^{5}

Since

|Ψ_{E}⟩is __not__ a stationary state with respect to *H _{A-B}*, unless the Hamiltonian is completely degenerate . Unfortunately, the completely degenerate Hamiltonian is useless in distinguishing a specific state, since it views any state as stationary. However, consider as an alternative the evolution of the system stabilized by a heat bath at constant temperature

Here, *S*[ρ_{A}]= -*Tr*[ρ_{A}logρ_{A}] is the von Neumann entropy. Note that *S*[ρ_{A}]= *S*[ρ*B*] because the entropy depends on the nonzero eigenvalues of the mixed state which are equal for both subsystems. Also, since *Tr*[ρ_{A}]=1=*const*, we may assume without any change to the dynamics that *S*(*x*)= -*x* log *x*+ *x* ,so that -*S*’(*x*)= log *x*. Now, Ψ_{E} will be stationary with respect to the functional *A* provided it satisfies the Euler-Lagrange equation

and this implies:

Recall that {*s _{n}*} is constrained by the fact that Ψ

We have discussed novel algebraic and computational structures based on the concept of Eratosthenian matrices (*E*-matrices) and Eratosthenian quantum states (*E*-states). We have observed that *E*-matrices furnish a noncommutative extension of the classical Dirichlet ring. We have also considered the task of initializing and manipulating *E*-states on a quantum computer and introduced an algorithm that implements the Dirichlet product of quantum state vectors. In addition, we have pointed out that if a method was known for efficient initialization of *E* -matrices with targeted narrow supports it would facilitate efficient factorization of integers.

I acknowledge the support of the Canadian Foundation for Innovation, grant LOF # 22117. I am grateful to an anonymous reviewer of this work for the suggestion of the relevance of the *approximate quantum Fourier transform*.

^{1}Note that *D _{N}* with N finite inherit the Dirichlet multiplication with obvious modifications. These are the only objects that one can hope to implement numerically.

^{2}An example of this type of a quantum system is a decoupled spin-pair in an NMR experiment.

^{3}The transposition stems from the fact that we adhere to the conventional organization of the quantum circuit operations. A reversal of the order of the registers results in an E-matrix as defined in Section 2.

^{4}In fact a harder problem is considered in [15], which is implementation of a state where |αx|2 stems from a discretization of a continuous probability distribution. Also, the reader will note that we have modified the original design by the usual shift of the register index.

^{5}We emphasize that HA-B is to be distinguished from Hcomp.

- Shor PW (1997) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Computing 26: 1484-1509.
- Bernstein E, Vazirani U (1997) Quantum Complexity Theory. SIAM J Comput 26: 1411-1473.
- Jack Copeland B (2004) The Essential Turing. The ideas that gave birth to the computer age. Oxford Press, Clarendon.
- Sowa A (2011) A fast-transform basis with hysteretic features. IEEE Conference Proceedings: Electrical and Computer Engineering (CCECE) 253-257.
- Sowa A (2013) The Dirichlet ring and unconditional bases in
*L*2[0,2p] Func. Anal Appl 47: 227-232. - Sowa A (2013) Factorizing matrices by Dirichlet multiplication. Lin Alg Appl 438: 2385-2393.
- Chandrasekharan K (1970) Arithmetical Functions. Springer-Verlag, Berlin.
- Kasch F (1982) Modules and Rings. Academic Press, London, New York.
- Brassard G, Høyer P, Mosca M, Tapp A (2002) Quantum Amplitude Amplification and Estimation, in: Conterporary Mathematics305Quantum Computation and Information. Amer Math Soc.
- Nielsen MA, Chuang IL (2000) Quantum Computation and Quantum Communication.Cambridge University Press,United Kingdom.
- Vedral V, Barenco A, Ekert A (1996) Quantum networks for elementary arithmetic operations. Phys Rev A 54:147-153.
- Florio G, Picca D(2004)Quantum implementation of elementary arithmetic operations.Cornell university Library.
- Rieffel E, Polak W (2011) Quantum Computing. The MIT Press: Cambridge, Massachusetts, London.
- Harrow AW, Hassidim A, Lloyd S (2009) Quantum algorithm for linear systems of equations. Phys Rev Lett 103: 150502.
- Grover L, Rudolph T (2002) Creating superpositions that correspond to efficiently integrable probability distributions.Cornell university Library.
- Barenko A, Ekert A, Suominen KA, Törmä P (1996) Approximate quantum Fourier transform and decoherence. Phys Rev A 54: 139-146.
- Sowa A (2009) Stationary states in nonlocal type dynamics of composite systems. J Geom Phys 59: 1604-1612.
- Sowa A (2011) Spectra of nonlocally bound quantum systems. Russ J Math Phys 18: 227-241.

Select your language of interest to view the total content in your interested language

- Algebraic Geometry
- Analytical Geometry
- Axioms
- Behaviometrics
- Big Data Analytics
- Binary and Non-normal Continuous Data
- Binomial Regression
- Biometrics
- Biostatistics methods
- Clinical Trail
- Complex Analysis
- Cross-Covariance and Cross-Correlation
- Differential Equations
- Fourier Analysis
- Genetic Linkage
- Hamilton Mechanics
- Hypothesis Testing
- Integration
- Large-scale Survey Data
- Matrix
- Microarray Studies
- Multivariate-Normal Model
- Noether's theorem
- Non rigid Image Registration
- Physical Mathematics
- Quantum Mechanics
- Quantum electrodynamics
- Regressions
- Relativity
- Riemannian Geometry
- Robust Method
- Soft biometrics
- Spatial Gaussian Markov Random Fields
- Statistical Methods
- Theoretical Physics
- Theory of Mathematical Modeling
- Topology
- mirror symmetry
- vector bundle

- Total views:
**9520** - [From(publication date):

June-2016 - Oct 22, 2019] - Breakdown by view type
- HTML page views :
**9296** - PDF downloads :
**224**

**Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals**

International Conferences 2019-20