Composed Operators

This section introduces the unitary operators needed by the Shor algorithm presented in section 3.3.

Pseudo-classic Operators

Simple Bit-Manipulations

Reverting Registers

The flip operator reverts the bit order of a register.

$$\mathtt{flip} : {\vert b_1,b_2\ldots b_n \rangle}\,\to\, {\vert b_n,b_{n-1}\ldots b_1 \rangle}$$ (3.12)

qufunct flip(qureg q) { // pseudo classic op to swap bit order
  int i;                // declare loop counter
  for i=0 to #q/2-1 {   // swap 2 symmetric bits
    Swap(q[i],q[#q-i-1]);
  }
}

Conditional Exclusive Or

The cxor operator has the functionality of a conditional CNot-based $\mathit{FANOUT}$ operation:

$$\mathtt{cxor} : {\vert a \rangle}_\mathbf{a}{\vert b \ran... ...gle}_\mathbf{e} & \;\mbox{otherwise} \\ \end{array}\right.$$ (3.13)

qufunct cxor(quconst a,qureg b,quconst enable) {
  int i;
  for i=0 to #a-1 {
    CNot(b[i],a[i] & enable);
  }
}

Comparing Registers

Comparing two classical binary numbers $a$ and $b$ can be simply achieved by comparing form the highest to the lowest bits and returning at the first mismatch.

for i=n-1 to 0 { // check whether b<a
  if bit(b,i)<bit(a,i) { return true; }
}
return false;

It is, however, not so trivial if one of the values is a quantum register $\mathbf{b}$, due to the lack of conditional branching. So, since we can't simply return form the loop, we have to look for another solution.

One possibility is to emulate an early return from the loop by using conditional operators (see section 1.3.5): For each bit comparison, we use an enable bit which is set to 1 if the bits are equal (and the loop has to continue) or to 0 if the result is decided and further comparisons should be disabled.

To compare an $n$ qubit register $\mathbf{b}$ to a classical integer $a$, we have to use an $n-1$ junk register $\mathbf{j}$ to store the enable bits. The main loop of the quantum comparison $\mathbf{b}<a$ then runs a follows.

for i=#b-2 to 1 step -1 {      // continue for lower bits
  if bit(a,i) {                // set new junk bit if undecided
    CNot(j[i-1],j[i] & b[i]);
    Not(b[i]);                 // honour last junk bit and
    CNot(flag,j[i] & b[i]);    // set result flag if a[i]>b[i]
  } else {
    Not(b[i]);
    CNot(j[i-1],j[i] & b[i]);
  }
  Not(b[i]);                   // restore b[i] again
}

For the complete implementation of the lt operator, as used in modular addition, please refer to appendix 3.2.1.2.

Multiplexed Adder

A multiplexed adder adds one of two classical bits $a_0$ and $a_1$ to a qubit $\mathbf{b}$, depending on the content of a selection qubit $\mathbf{s}$. The target register $\mathbf{y}_{sum}=(\mathbf{c}_{in},\mathbf{c}_{out})$ consists of a carry-in and a carry-out qubit, to allow cascading. The truth table for the operation is:

$\mathbf{s}$	$a_0$	$a_1$	$a_\mathbf{s}$
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

$a_\mathbf{s}$	$\mathbf{b}$	$\mathbf{c}_{in}$	$\mathbf{c'}_{in}$	$\mathbf{c'}_{out}$
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

The implementation of the truth-table with controlled-not gates (muxaddbit) is straightforward and can be found in appendix A.3.^3.1 A multiplexed adder for registers can be constructed by cascading several single bit adders:

qufunct muxadd(int a0,int a1,qureg sel,quconst b,quvoid sum,quconst e) { 
  int i;
  for i=0 to #b-2 {           // fulladd first #b-1 bits
    muxaddbit(bit(a0,i),bit(a1,i),sel,b[i],sum[i:i+1],e);
  }                           // half add last bit
  muxaddbit(bit(a0,#b-1),bit(a1,#b-1),sel,b[#b-1],sum[#b-1],e);
}

Modular Arithmetic

Many number theoretic algorithms describe calculations in the remainder class $\mathbf{Z}_n$. On example for a quantum algorithm using modular arithmetic, is Shor's method of polynomial time quantum factoring (see section 3.3).[11].

For a more detailed discussion of unitary operators for modular arithmetic, please refer to [13].

Modular Addition

The addition modulo $n$ of a classic integer $a$ and a quantum register $\mathbf{b}$ can result in either $a+b$ or $(a-n)+b)$, depending on the particular base-vector ${\vert b \rangle}$.

While for $b<n$ the operation is revertible, this is not the case for $b\geq n$, so, if $n$ doesn't happen to be a power of $2$, besides the target resister $\mathbf{y}_s$ for the sum, we need an additional flag-qubit $\mathbf{y}_y$ to allow for a quantum function addn which is both, unitary and invariant to $\mathbf{b}$:

$$\mathtt{addn}_{a,n} : {\vert b \rangle}_\mathbf{b}{\vert ... ...y}_{flag}} & \;\mbox{if}\, a+b \geq n \\ \end{array}\right.$$ (3.14)

By using the less-than operator lt and the multiplexing adder muxadd, the implementation is rather straightforward. (The enable register $\mathbf{e}$ has been added to allow the use for modular multiplication; see below.)

qufunct addn(int a,int n,quconst b,quvoid flag,quvoid sum,quconst e) {
  qureg s=sum[0\#b-1];
  qureg f=sum[#b-1];
  qureg bb=b;                      // "abuse" sum and b as scratch
  lt(n-a,bb,f,s);                  // for the less-than operator
  CNot(flag,f & e);                // save result of comparison
  !lt(n-a,bb,f,s);                 // restore sum and b
  muxadd(2^#b+a-n,a,flag,b,sum,e); // add either a or a-n
}

The only trick here is, that we redeclare the quconst $\mathbf{b}$ as qureg, so that we can use a ``dirty'' implementation of lt which doesn't perform any cleanup on $\mathbf{b}$ or $\mathbf{y}_s$ (sum), which would be pointless anyway, since the comparison gets uncomputed after the result has been saved.

Since $\mathtt{addn}_{n-a,n}$ is a quantum function for modular subtraction and thus implements the inverse function $f^{-1}_{a,n}(b)=b-a \,{\rm mod}\,n$ to $f_{a,n}=a+b\, \,{\rm mod}\,n$, we can construct an overwriting version oaddn of modular addition, by using the method introduced in section 1.3.4.3:

$$F': {\vert i,0 \rangle} \stackrel{U_f}{\longrightarrow} ... ...{U^\dagger _{f^{-1}}}{\longrightarrow} {\vert f(i),0 \rangle}$$ (3.15)

$\mathtt{addn}_{n-a,n}$ doesn't invert the overflow flag $\mathbf{y}_f$, so we have to switch it manually:

$$U^\dagger _{f^{-1}}=\mathtt{addn}_{n-a,n}(\mathbf{b},\mathbf{y}_s, \mathbf{y}_f)$$ (3.16)

The original target registers $\mathbf{y}_s$ and $\mathbf{y}_f$ can now be allocated as unmanaged local scratch.

qufunct oaddn(int a,int n,qureg sum,quconst e) {
  qureg j[#sum];
  qureg f[1];
  
  addn(a,n,sum,f,j,e);             // junk -> a+b mod n
  Swap(sum,j);                     // swap junk and sum
  CNot(f,e);                       // toggle flag
  !addn(n-a,n,sum,f,j,e);          // uncompute b to zero
}

Modular Multiplication

Modular multiplication is merely a composition of conditional additions for each qubit of $\mathbf{b}$ since

$$ab\,\,{\rm mod}\,n=\sum_{i=0}^{\lceil\mathrm{ld}\,b\rceil}\... ...2^i a \,{\rm mod}\,n\right) \quad{\rm with}\quad b_i\in{\bf B}$$ (3.17)

The first summand can be slightly optimised, since the accumulator (prod) is still empty.

qufunct muln(int a,int n,quconst b,qureg prod,quconst e) {
  int i;
  
  for i=0 to #prod-1 {
    if bit(a,i) { CNot(prod[i],b[0] & e); }
  }
  for i=1 to #b-1 {
    oaddn(2^i*a mod n,n,prod,b[i] & e);
  }
}

As above, we can construct an overwriting version, if an implementation of the inverse function exists. This is the case if $\gcd(a,n)=1$ so $a$ and $n$ are relatively prime, because then the modular inverse $a^{-1}$ with $a^{-1}a \,{\rm mod}\,n=1$ exists. Since we intend to use the operator for the Shor algorithm which demands that $\gcd(a^k,n)=1$, this is good enough for us.

By using two conditional XOR gates (see section 3.2.1.1) for swapping the registers^3.2we can implement a conditional $\mathtt{omuln}_{[[\mathbf{e}]],a,n}{\vert b \rangle}\to{\vert ab\,\,{\rm mod}\,n \rangle}$

qufunct omuln(int a,int n,qureg b,quconst e) {
  qureg j[#b];

  muln(a,n,b,j,e);
  !muln(invmod(a,n),n,j,b,e);
  cxor(j,b,e);
  cxor(b,j,e);
}

Modular Exponentiation

As with muln, we can construct modular exponentiation by conditionally applying omuln with the qubits of the exponents as enable string, according to

$$a^b\,\,{\rm mod}\,n=\prod_{i=0}^{\lceil\mathrm{ld}\,b\rceil... ...,b_i} \,{\rm mod}\,n\right) \quad{\rm with}\quad b_i\in{\bf B}$$ (3.18)

Before we can start the iteration, the accumulator (ex) has to be initialised by 1.

qufunct expn(int a,int n,quconst b,quvoid ex) {
  int i;
  
  Not(ex[0]);                            // start with 1
  for i=0 to #b-1 {
    omuln(powmod(a,2^i,n),n,ex,b[i]);    // ex -> ex*a^2^i mod n
  }
}

Quantum Fourier Transform

For a $q$ dimensional vector ${\vert\psi \rangle}$, the discrete Fourier transform is defined as

$$\mathit{DFT}:{\vert x \rangle}\,\to\,\frac{1}{\sqrt{q}} \sum_{y=0}^{q-1} e^{\frac{2\pi i}{q}\,xy} \,{\vert y \rangle}$$ (3.19)

Since ${\vert\psi \rangle}$ is a combined state of $n$ qubits, $q$ is always a power of 2. The classical fast Fourier Transform ($\mathit{FFT}$) uses a binary decomposition of the exponent to perform the transformation in $O(n2^n)$ steps.

As suggested by Coppersmith [7], the same principle could adapted be to quantum computers by using a combination of Hadamard transformations $H$ and conditional phase gates $V$ (indices indicate the qubits operated on):

$$\mathit{DFT'}= \prod_{i=1}^{n-1}\left( H_{n-i-1}(\frac{\pi... ...1} V_{n-i-1,n-j-1}(\frac{2\pi}{2^{i-j+1}}) \right)\;H_{n-1}$$ (3.20)

$\mathit{DFT'}$ iterates the qubits form the MSB to the LSB, ``splits'' the qubits with the Hadamard transformation and then conditionally applies phases according to their relative binary position ( $e^\frac{2\pi\mathrm{i}}{2^{i-j+1}}$) to each already split qubit.

The base-vectors of the transformed state ${\vert\tilde{\psi}' \rangle}=\mathit{DFT'}\,{\vert\psi \rangle}$ are given in reverse bit order, so the get the actual $\mathit{DFT}$, the bits have to be flipped.

operator dft(qureg q) { // main operator
  const n=#q;           // set n to length of input
  int i; int j;         // declare loop counters
  for i=0 to n-1 {
    for j=0 to i-1 {    // apply conditional phase gates
      CPhase(2*pi/2^(i-j+1),q[n-i-1] & q[n-j-1]);
    }
    Mix(q[n-i-1]);      // qubit rotation
  }    
  flip(q);              // swap bit order of the output
}

Footnotes

...qufunct.qcl.^3.1

muxaddbit is actually a conditional version with an additional enable register $\mathbf{e}$, as it is needed for modular multiplication

... registers^3.2

normally, 3 XOR operations are necessary to swap a register, but since one register is empty, 2 XORs suffice.