org.mathIT.quantum

Class QuantumToolBox

java.lang.Object

org.mathIT.quantum.QuantumToolBox

public class QuantumToolBox
extends Object

This class provides utilities for quantum computation and quantum algorithms.

Version:

1.1

Author:

Andreas de Vries

Method Summary

Modifier and Type	Method and Description
static long	order(double z, long a, long n, int limit) Given the number z ≈ s/r as information, where r is the order modulo n of the number a, and 0 <= s < r (but not knowing neither s nor r), this method returns a multiple of r if such a number is found, or -1 otherwise.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

order

public static long order(double z,
                         long a,
                         long n,
                         int limit)

Given the number z ≈ s/r as information, where r is the order modulo n of the number a, and 0 <= s < r (but not knowing neither s nor r), this method returns a multiple of r if such a number is found, or -1 otherwise. The method is used by Shor's quantum algorithm for integer factorization where n denotes the number to be factorized, z is the measurement result of the quantum register, and a is a random number satisfying 1 < a < n. The method utilizes continued fractions to approximate z. By the quantum mechanical laws and by the construction of Shor's algorithm, it is guaranteed in principle that z is a rational number and hence the method terminates. However, by the finite precision of the data type of z, a limit of maximum continued fraction coefficients is required to let the method terminate certainly. Some small number triples for which these requirements are satisfied, are the following:

• z = 2867./4096, a = 5, n = 33 (r = 10);
• z = 1536./2048, a = 4, n = 15 (r = 4);
• z = 13453./16384, a = 3, n = 91 (r = 6);

For details see M.A. Nielsen, I.L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge 2000, §5.3.1

Parameters:

z - a number approximating the unknown rational number s/r

a - a previously randomly chosen test number

n - the modulus

limit - the maximum number of continued fraction coefficients to be computed

Returns:

a multiple of the order r of a mod n

See Also:

Numbers.continuedFraction(double,int), Numbers.ord(long,long)