Walter O. Krawec
Download Q-Prog (Source and Windows Binaries): (ZIP) 300KB. Current version is 0.81.4.13; released April 2013.
Download Sample Programs (Source only): Coming Soon
Download "Simulating Quantum Algorithms with Q-Prog": (PDF) 211KB.
This page describes Q-Prog (Quantum Programmer); an interpreter allowing the user to program and then simulate quantum algorithms over arbitrary dimensional spaces.
Q-Prog has been tested on Windows 7 (build using MS VC++ 2010), Mac OS X, and Linux. You may find the full source code for Q-Prog along with a Windows binary at the above download link. The download file contains several test programs including Shor's Factorization problem and a Quantum Walk over the integers. The second link (sample programs) contains more complicated examples referenced in the paper "Simulating Quantum Algorithms with Q-Prog".
History:
April 13, 2013: Released v.81. No longer need integer or double constructors (though they are still supported). Fixed a bug with the "file" command. Also fixed an issue with the VC++2010 solution file.
The following script solves Deutsch's problem for a 1 qubit input. In particular, if given a function "f" that is either
constant or symmetric (in our case f(0) = f(1) or f(0) \ne f(1)), the Deutsch problems asks if we can determine which type "f" is.
Classically, we would have to poll the function twice to determine the answer. However using quantum computers we may determine
the type of function "f" with only a single query.
begin
(new space Qubit (integer 2) )
(new matrix psi (integer 1) (integer 1) )
(new matrix Uf (integer 4) (integer 4) )
(NOP Uf is the function gate; i.e. the gate that computes "f(x)")
(NOP In this example, we have f(x) = x; the identity matrix)
(set Uf (matrix (integer 4) (integer 4) ident) )
(NOP Set the initial state \ket{\psi} = \ket{00})
(set psi (tensor (get Qubit.ket.0) (get Qubit.ket.0) ) )
(NOP Run the algorithm:)
(set psi (mult (tensor (get X2) (get X2) ) (get psi) ) )
(set psi (mult (tensor (get H2) (get H2) ) (get psi) ) )
(set psi (mult (get Uf) (get psi) ) )
(set psi (mult (tensor (get H2) (matrix (integer 2) (integer 2) ident) ) (get psi) ) )
(new complex sum)
(set sum (complex 0 0) )
(set sum (add (get sum) (cnorm (mult (tensor (get Qubit.bra.0) (get Qubit.bra.0) ) (get psi) ) ) ) )
(set sum (add (get sum) (cnorm (mult (tensor (get Qubit.bra.0) (get Qubit.bra.1) ) (get psi) ) ) ) )
(NOP If we measured the last most sig. qubit as "0", then sum = 1 and the fct. is symmetric so print that)
(NOP else we measured a "1" (hence sum=0) so print the fct. is constant)
(if (comp.less (real (get sum) ) (double 0.5) ) (print (function-is-constant) ) (print (function-is-not-constant) ) )
Quantum Random walks are described in (Kempe, 2008) and (Krovi, Brun, 2008). The following script simulates a walk over
Z/250Z (integers modulo 250). We graph the probability distribution later; note that this agrees with the results of (Kempe, 2008) (technically they were looking at
a walk over the integers but since we stop the walk after 100 iterations therefore there is no roll-over, the result is the same).
begin (new integer N) (new integer T) (new integer start) (print Specify-Position-Size:) (set N (user.input integer) ) (print Specify-Number-of-Iterations:) (set T (user.input integer) ) (set start (div (get N) (integer 2) ) ) (new space Coin (integer 2) ) (new space Position (get N) ) (new system H (integer 2) Coin Position) (new matrix Shift (integer 1) (integer 1) ) (new matrix temp-mat (integer 1) (integer 1) ) (set temp-mat (matrix (get N) (get N) zero) ) (new integer i) (set i (integer 0) ) (while (comp.lt (get i) (get N ) ) (set temp-mat (add (get temp-mat) (mult (get (index Position.ket (mod (subtract (get i) (integer 1) ) (get N) ) ) ) (get (index Position.bra (get i) ) ) ) ) ) (set i (add (get i) (integer 1) ) ) ) (set Shift (tensor (mult (get Coin.ket.0) (get Coin.bra.0) ) (get temp-mat) ) ) (set i (integer 0) ) (set temp-mat (matrix (get N) (get N) zero) ) (while (comp.lt (get i) (get N ) ) (set temp-mat (add (get temp-mat) (mult (get (index Position.ket (mod (add (get i) (integer 1) ) (get N) ) ) ) (get (index Position.bra (get i) ) ) ) ) ) (set i (add (get i) (integer 1) ) ) ) (set Shift (add (get Shift) (tensor (mult (get Coin.ket.1) (get Coin.bra.1) ) (get temp-mat) ) ) ) (NOP Now run the walk) (new matrix psi (integer 1) (integer 1) ) (new matrix U (integer 1) (integer 1) ) (set psi (tensor (get Coin.ket.0) (get (index Position.ket (get start) ) ) ) ) (set U (matrix (integer 2) (integer 2) QFT) ) (set i (integer 0) ) (while (comp.lt (get i) (get T) ) (set psi (apply_op (get H) (integer 0) (get U) (get psi) ) ) (set psi (mult (get Shift) (get psi) ) ) (set i (add (get i) (integer 1) ) ) ) (new array P-dist double (get N) ) (measure_distribution (get psi) (get H) (integer 1) P-dist)
We also embedded Q-Prog in a custom-made graphing application to view the evolution of the distribution over the particle's position with time. Click here to watch this video.
After running the program with PSize=250, t=100, we graphed the points in "graph.txt" (using Excel):
Example 3 - Shor's Algorithm
The following script finds the period of the function f(x) = b^x (mod N) using Shor's algorithm.
begin
(new integer p)
(new integer q)
(new integer N)
(new integer b)
(set b (integer 7) )
(set p (integer 3) )
(set q (integer 5) )
(set N (mult (get p) (get q) ) )
(nop n0 is smallest int s.t. 2^n0 > pq)
(new integer n0)
(new integer two_n0)
(set n0 (integer 4) )
(set two_n0 (pow2 (get n0) ) )
(new integer n)
(new integer two_n)
(set n (mult (get n0) (integer 2) ) )
(set two_n (pow2 (get n) ) )
(new space Qubit (integer 2) )
(new space InputRegister (get two_n) )
(new space OutputRegister (get two_n0) )
(nop first compute ket{x}ket{f(x)} for all x)
(new matrix psi (mult (get two_n) (get two_n0) ) (integer 1) )
(new integer i)
(set i (integer 0) )
(while (comp.lt (get i) (get two_n) )
(set psi (add (get psi) (tensor (get_index InputRegister.ket (get i) ) (get_index OutputRegister.ket (powm (get b) (get i) (get N) ) ) ) ) )
(set i (add (get i) (integer 1) ) )
(print (get i) )
)
(set psi (mult (inv (pow2 (get n0) ) ) (get psi) ) )
(new_file psi0.txt)
(print_file (psi0.txt) (get psi) )
(NOP now measure output register)
(set i (integer 0) )
(new matrix UFT (integer 1) (integer 1) )
(set UFT (matrix (get two_n) (get two_n) UFT) )
(while (comp.lt (get i) (get n0) )
(set psi (measure_qbit (get psi) (add (get i) (integer 0) ) ) )
(set i (add (get i) (integer 1) ) )
(print (get i) )
)
(set i (integer 0) )
(new integer input_measure)
(nop while (comp.lt (get i) (get n) )
(set psi (measure_qbit (get psi) (add (get i) (get n0) ) (input_measure) ) )
(set i (add (get i) (integer 1) ) )
(print (get i) )
)
(set psi (mult (tensor (get UFT) (matrix (get two_n0) (get two_n0) ident) ) (get psi) ) )
(print (Measuring) )
(set i (integer 0) )
(new integer output_measure)
(new integer outputResult)
(new matrix psi2 (integer 1) (integer 1) )
(set psi2 (get psi) )
(while (comp.lt (get i) (get n) )
(set psi2 (measure_qbit (get psi2) (add (get i) (get n0) ) (output_measure) ) )
(set outputResult (add (get outputResult) (mult (get output_measure) (pow2 (get i) ) ) ) )
(set i (add (get i) (integer 1) ) )
(print (get i) )
)
(new integer done)
(new integer outputResult2)
(set done (integer 1) )
(while (get done)
(set psi2 (get psi) )
(set outputResult2 (integer 0) )
(set i (integer 0) )
(while (comp.lt (get i) (get n) )
(set psi2 (measure_qbit (get psi2) (add (get i) (get n0) ) (output_measure) ) )
(set outputResult2 (add (get outputResult2) (mult (get output_measure) (pow2 (get i) ) ) ) )
(set i (add (get i) (integer 1) ) )
)
(if (comp.ne (get outputResult) (get outputResult2) ) (set done (integer 0) ) (nop) )
)
(print (get outputResult) )
(print (get outputResult2) )
(print (the-period-r-is-an-integer-times:) )
(print (div_d (get two_n) (get outputResult) ) )
(print (also-the-period-r-is-an-integer-times:) )
(print (div_d (get two_n) (get outputResult2) ) )
The following is sample output of the program setting b = 7, N = 15 (N = 3 x 5). The program reports that the period "r" is an integer times 2 and an integer times 4. In actuality, the period in this example is r = 4 (7^0 = 1; 7^1=7; 7^2=4; 7^3=13; 7^4=1; ...)
integer outputResult = 128 integer outputResult2 = 64 string temp = the-period-r-is-an-integer-times: double temp = 2 string temp = also-the-period-r-is-an-integer-times: double temp = 4