Tag: QFT

QHack 2023: 4 week prep-challenge, day 23, Draper adder

I went for another QOSF task (Oct. 2022), there I tackled the seemingly easy task of implementing a Draper adder, as an intermediate step towards a multiplier. However, I got lost in index engineering. At this point, I am not satisfied with the solution, but the tests check out, so it is usable.

I added two quantum registers; instead of the much easier multiplication of a quantum with a classical register.

import pennylane as qml
from pennylane import numpy as np

reg_size = 4
n_wires = 2*reg_size

dev = qml.device("default.qubit", wires=n_wires)

def base_encode(a, wires_offset=0):
    a_bin = np.binary_repr(a, reg_size)
    a_bin = a_bin if wires_offset else reversed(a_bin)
    
    for i, ai in enumerate(a_bin):
        if ai == "1":
            qml.PauliX(i + wires_offset)

@qml.qnode(dev)
def circuit(a, b):
    
    # encode basis state
    base_encode(a)
    base_encode(b, wires_offset=reg_size)
    
    # apply QFT to one register
    qml.QFT(wires=range(reg_size, n_wires))
    
    # in this implementation, I pretend that I do not know the value of b, 
    # this could be the case, if this addition was amidst a longer calculation
    for i in range(reg_size): # ith significant bit (target)
        for j in range(reg_size-i): # control bits
            trgt_idx = n_wires - 1 - i
            ctrl_idx = trgt_idx - reg_size - j
            angle = np.pi/(2**j)
            qml.ControlledPhaseShift(angle, wires=[ctrl_idx, trgt_idx])
    
    # invert QFT
    qml.adjoint(qml.QFT)(wires=range(reg_size, n_wires))
    
    return qml.probs(wires=range(reg_size, n_wires))# [qml.expval(qml.PauliZ(i)) for i in range(reg_size, n_wires)]

As already mentioned, I wouldn’t trust the implementation, if the tests didn’t check out, but they do.

circ_draw = qml.draw(circuit)

res = np.array([])
for a in range(reg_size**2 - 1):
    for b in range(reg_size**2 - 1 -a):
        sample = circuit(a, b)
        expected_result = a+b
        if np.argmax(sample)!=expected_result:
            print(f"a: {a}, b: {b}, sample: {np.argmax(sample)}")
            print(circ_draw(a, b))
            break
        
        res = np.append(res, [np.argmax(sample)==a+b])
        
print(f"The algorithm is correct! {len(res)} tests successful!" if np.all(res) else "There is an error")

QHack 2023: 4 week prep challenge, day 11, A Quantum Adder (QFT)

Today, I’m continuing with the next exercise from the algorithms track. The task is to build a number adder using the Fourier space.

Firstly, a Fourier transform is applied on the initial state, i.e. a state |0> or |1> in the computational basis is flipped into the X-Y-plane. The qubits are then rotated around the Z-axis, with an angle according to the number to add. Eventually, the state is transformed back from the Fourier space.

The transformation rule for the QFT reads

\[ QFT|x\rangle = \frac{1}{\sqrt{M}} \sum^{M-1}_{k=0} \exp(\frac{2 \pi i}{M} x k) |k\rangle \]

If you now want to add to a state in the Fourier space, you have to rotate the qubits accordingly. It is important to notice, that a rotation only effects the |1> portion, but not the |0> portion of a qubit’s state.

Having that in mind, it was relatively straight forward to come up with the solution…

def qfunc_adder(m, wires):
    """Quantum function capable of adding m units to a basic state given as input.

    Args:
        - m (int): units to add.
        - wires (list(int)): list of wires in which the function will be executed on.
    """

    qml.QFT(wires=wires)

    for w, _ in enumerate(wires):
        angle = m*np.pi/(2**w)
        qml.RZ(angle, wires=w)

    qml.QFT(wires=wires).inv()

… the tests check out, success!