Bitonic sort¶

In this notebook we:

• demonstrate the use of a Qubrick as implemented in Workbench Algorithms corresponding to bitonic sort
• briefly describe a procedure to uncompute sort-like subroutines
• use a state vector sim to inspect and confirm that we indeed have prepared a sorted state

Sorting a list is a ubiquitous computational primitive. There exist enormous numbers of families of methods for sorting, let alone individual methods across families.

One prominent type of sorting algorithm is the bitonic sort ⧉. As with most sorts, this method makes use of networks of comparisons, where one compares the value of two elements and conditionally swap those two elements.

Sorting on a QPU¶

In Workbench, we have a BitonicSort routine corresponding to this primitive. Analogously to its classical counter part, it makes use of comparator circuits and controlled swap gates to sort in either a descending or ascending order (set by the user).

Let's see this in action.

In [1]:

from psiqworkbench import QPU, Qubits, Qubrick
from psiqworkbench.filter_presets import BIT_DEFAULT
import numpy as np
from workbench_algorithms import BitonicSort
from workbench_algorithms.utils import total_sort_num_comps
from random import randint
import numpy as np

%load_ext autoreload

%autoreload 2

from psiqworkbench import QPU, Qubits, Qubrick from psiqworkbench.filter_presets import BIT_DEFAULT import numpy as np from workbench_algorithms import BitonicSort from workbench_algorithms.utils import total_sort_num_comps from random import randint import numpy as np %load_ext autoreload %autoreload 2

In [2]:

size_int = 3  # number of bits per int on target register
num_int = 5  # number of integers to sort
direction = 0  # 0-ascending, 1-descending sort

# determine number of qubits in sim
num_target = num_int * size_int
num_anc = total_sort_num_comps(num_int)  + size_int
num_qbits = num_target + num_anc

# totally classical logic; can turn off the state sim (and try huge instances)
qc = QPU(filters=BIT_DEFAULT)
qc.reset(num_qbits)

# write random vals to target reg
unsorted_vals = [randint(0, 2**size_int - 1) for x in range(num_int)]
target_reg = [Qubits(size_int, "val_" + str(i), qc) for i in range(num_int)]
for i in range(0, num_int):
    target_reg[i].write(unsorted_vals[i])

# do the sort
bit_sort = BitonicSort()
bit_sort.compute(target_reg, direction)

# 1 is descending sort...
if direction == 1:
    sorted_vals = sorted(unsorted_vals, reverse=True)
# ... 0 is ascending sort
else:
    sorted_vals = sorted(unsorted_vals)

# check measured vals on target reg are indeed ordered
for i in range(num_int):
    assert target_reg[i].read() == sorted_vals[i]

# draw circuit
qc.draw()

size_int = 3 # number of bits per int on target register num_int = 5 # number of integers to sort direction = 0 # 0-ascending, 1-descending sort # determine number of qubits in sim num_target = num_int * size_int num_anc = total_sort_num_comps(num_int) + size_int num_qbits = num_target + num_anc # totally classical logic; can turn off the state sim (and try huge instances) qc = QPU(filters=BIT_DEFAULT) qc.reset(num_qbits) # write random vals to target reg unsorted_vals = [randint(0, 2**size_int - 1) for x in range(num_int)] target_reg = [Qubits(size_int, "val_" + str(i), qc) for i in range(num_int)] for i in range(0, num_int): target_reg[i].write(unsorted_vals[i]) # do the sort bit_sort = BitonicSort() bit_sort.compute(target_reg, direction) # 1 is descending sort... if direction == 1: sorted_vals = sorted(unsorted_vals, reverse=True) # ... 0 is ascending sort else: sorted_vals = sorted(unsorted_vals) # check measured vals on target reg are indeed ordered for i in range(num_int): assert target_reg[i].read() == sorted_vals[i] # draw circuit qc.draw()

The uncomputation for this Qubrick is not merely the dagger of the compute; instead, here we have an example of measurement-based uncomputation.

Uncomputation can be performed by looping over all comparator-swaps in reverse order. For each record qubit k associated with the comparison of registers a and b;

1. Swap a and b controlled on k
2. Measure the record qubit in the X basis; a. If the outcome is zero, the record qubit as been uncomputed (step 1 with the next record qubit, k - 1) b. If the outcome is one, we need to perform a phase correction (step 3)
3. Perform another comparison between a and b; let's denote the result of this comparison as k'
4. Apply a Z gate on k'
5. Uncompute the comparator

To demonstrate the uncomputation, let's use an input state in superposition.

In [3]:

size_int = 3  # number of bits per int on target register
num_int = 3  # number of integers to sort
direction = 1  # 0-ascending, 1-descending sort

# determine number of qubits in sim
num_target = num_int * size_int
num_anc = total_sort_num_comps(num_int)  + size_int
num_qbits = num_target + num_anc

# totally classical logic; can turn off the state sim (and try huge instances)
qc = QPU()
qc.reset(num_qbits)

# write random vals to target reg
unsorted_vals = [randint(0, 2**size_int - 1) for x in range(num_int - 1)]
target_reg = [Qubits(size_int, "val_" + str(i), qc) for i in range(num_int)]

for i in range(num_int - 1):
    target_reg[i].write(unsorted_vals[i])
target_reg[-1].had()

print("Initial state: ")
qc.print_state_vector()
initial_state = qc.pull_state()

# do the sort
bit_sort = BitonicSort()
qc.label('Sort')
bit_sort.compute(target_reg, direction)
qc.label()

# 1 is descending sort...
if direction == 1:
    sorted_vals = sorted(unsorted_vals, reverse=True)
# ... 0 is ascending sort
else:
    sorted_vals = sorted(unsorted_vals)

# check measured vals on target reg are indeed ordered
print("Sorted state: ")
qc.print_state_vector()

qc.nop()
qc.nop()
qc.nop()

qc.label('Uncompute')
bit_sort.uncompute()
qc.label()

print("Uncomputed state: ")
qc.print_state_vector()

# Assert that we have recover the initial state
assert np.allclose(qc.pull_state(), initial_state)


qc.draw()

size_int = 3 # number of bits per int on target register num_int = 3 # number of integers to sort direction = 1 # 0-ascending, 1-descending sort # determine number of qubits in sim num_target = num_int * size_int num_anc = total_sort_num_comps(num_int) + size_int num_qbits = num_target + num_anc # totally classical logic; can turn off the state sim (and try huge instances) qc = QPU() qc.reset(num_qbits) # write random vals to target reg unsorted_vals = [randint(0, 2**size_int - 1) for x in range(num_int - 1)] target_reg = [Qubits(size_int, "val_" + str(i), qc) for i in range(num_int)] for i in range(num_int - 1): target_reg[i].write(unsorted_vals[i]) target_reg[-1].had() print("Initial state: ") qc.print_state_vector() initial_state = qc.pull_state() # do the sort bit_sort = BitonicSort() qc.label('Sort') bit_sort.compute(target_reg, direction) qc.label() # 1 is descending sort... if direction == 1: sorted_vals = sorted(unsorted_vals, reverse=True) # ... 0 is ascending sort else: sorted_vals = sorted(unsorted_vals) # check measured vals on target reg are indeed ordered print("Sorted state: ") qc.print_state_vector() qc.nop() qc.nop() qc.nop() qc.label('Uncompute') bit_sort.uncompute() qc.label() print("Uncomputed state: ") qc.print_state_vector() # Assert that we have recover the initial state assert np.allclose(qc.pull_state(), initial_state) qc.draw()

Initial state: 
|val_0|val_1|val_2|?>
|4|7|0|.>    0.353553+0.000000j
|4|7|1|.>    0.353553+0.000000j
|4|7|2|.>    0.353553+0.000000j
|4|7|3|.>    0.353553+0.000000j
|4|7|4|.>    0.353553+0.000000j
|4|7|5|.>    0.353553+0.000000j
|4|7|6|.>    0.353553+0.000000j
|4|7|7|.>    0.353553+0.000000j
Sorted state: 
|val_0|val_1|val_2|record_0|record_1|record_2|?>
|7|4|0|1|0|0|.>    0.353553+0.000000j
|7|4|1|1|0|0|.>    0.353553+0.000000j
|7|4|2|1|0|0|.>    0.353553+0.000000j
|7|4|3|1|0|0|.>    0.353553+0.000000j
|7|4|4|1|0|0|.>    0.353553+0.000000j
|7|5|4|1|1|0|.>    0.353553+0.000000j
|7|6|4|1|1|0|.>    0.353553+0.000000j
|7|7|4|1|1|0|.>    0.353553+0.000000j
Uncomputed state: 
|val_0|val_1|val_2|?>
|4|7|0|.>    0.353553+0.000000j
|4|7|1|.>    0.353553+0.000000j
|4|7|2|.>    0.353553+0.000000j
|4|7|3|.>    0.353553+0.000000j
|4|7|4|.>    0.353553+0.000000j
|4|7|5|.>    0.353553+0.000000j
|4|7|6|.>    0.353553+0.000000j
|4|7|7|.>    0.353553+0.000000j

If we ran the above cell multiple times, we might notice a different circuit each time. The number of c-swaps in the uncompte is identical to the number in compute. However, the number of comparators in uncompute might change from run to run. The number of comparator is expected to be around half of the number in compute, with the worst case being an identical number. Thus, in expectation, the uncompute should be cheaper than the compute, or at worst, as expensive.

The controlled version is also relatively cheap. For the compute, only the boolean result (a.k.a the record qubit) of the comparators needs to be controlled. For the uncompute, only the phase fix-up requires a control, which promotes a single qubit Z into a C-Z (a.k.a no added toffolis / Ts for a single-ctrl qubit!). Check this out:

In [4]:

size_int = 3  # number of bits per int on target register
num_int = 3  # number of integers to sort
direction = 0  # 0-ascending, 1-descending sort

# determine number of qubits in sim
num_target = num_int * size_int
num_anc = total_sort_num_comps(num_int)  + size_int
num_qbits = num_target + num_anc + 1

# totally classical logic; can turn off the state sim (and try huge instances)
qc = QPU()
qc.reset(num_qbits)

# write random vals to target reg
unsorted_vals = [randint(0, 2**size_int - 1) for x in range(num_int - 1)]
ctrl = Qubits(1, 'ctrl', qc)
target_reg = [Qubits(size_int, "val_" + str(i), qc) for i in range(num_int)]

for i in range(num_int - 1):
    target_reg[i].write(unsorted_vals[i])
target_reg[-1].had()

print("Initial state: ")
qc.print_state_vector()
initial_state = qc.pull_state()

# do the sort
bit_sort = BitonicSort()
qc.label('Sort')
bit_sort.compute(target_reg, direction, ctrl)
qc.label()

# 1 is descending sort...
if direction == 1:
    sorted_vals = sorted(unsorted_vals, reverse=True)
# ... 0 is ascending sort
else:
    sorted_vals = sorted(unsorted_vals)

# check measured vals on target reg are indeed ordered
print("Sorted state: ")
qc.print_state_vector()

qc.nop()
qc.nop()
qc.nop()

qc.label('Uncompute')
bit_sort.uncompute()
qc.label()

print("Uncomputed state: ")
qc.print_state_vector()

qc.draw()

size_int = 3 # number of bits per int on target register num_int = 3 # number of integers to sort direction = 0 # 0-ascending, 1-descending sort # determine number of qubits in sim num_target = num_int * size_int num_anc = total_sort_num_comps(num_int) + size_int num_qbits = num_target + num_anc + 1 # totally classical logic; can turn off the state sim (and try huge instances) qc = QPU() qc.reset(num_qbits) # write random vals to target reg unsorted_vals = [randint(0, 2**size_int - 1) for x in range(num_int - 1)] ctrl = Qubits(1, 'ctrl', qc) target_reg = [Qubits(size_int, "val_" + str(i), qc) for i in range(num_int)] for i in range(num_int - 1): target_reg[i].write(unsorted_vals[i]) target_reg[-1].had() print("Initial state: ") qc.print_state_vector() initial_state = qc.pull_state() # do the sort bit_sort = BitonicSort() qc.label('Sort') bit_sort.compute(target_reg, direction, ctrl) qc.label() # 1 is descending sort... if direction == 1: sorted_vals = sorted(unsorted_vals, reverse=True) # ... 0 is ascending sort else: sorted_vals = sorted(unsorted_vals) # check measured vals on target reg are indeed ordered print("Sorted state: ") qc.print_state_vector() qc.nop() qc.nop() qc.nop() qc.label('Uncompute') bit_sort.uncompute() qc.label() print("Uncomputed state: ") qc.print_state_vector() qc.draw()

Initial state: 
|ctrl|val_0|val_1|val_2|?>
|0|3|3|0|.>    0.353553+0.000000j
|0|3|3|1|.>    0.353553+0.000000j
|0|3|3|2|.>    0.353553+0.000000j
|0|3|3|3|.>    0.353553+0.000000j
|0|3|3|4|.>    0.353553+0.000000j
|0|3|3|5|.>    0.353553+0.000000j
|0|3|3|6|.>    0.353553+0.000000j
|0|3|3|7|.>    0.353553+0.000000j
Sorted state: 
|ctrl|val_0|val_1|val_2|record_0|record_1|record_2|?>
|0|3|3|0|0|0|0|.>    0.353553+0.000000j
|0|3|3|1|0|0|0|.>    0.353553+0.000000j
|0|3|3|2|0|0|0|.>    0.353553+0.000000j
|0|3|3|3|0|0|0|.>    0.353553+0.000000j
|0|3|3|4|0|0|0|.>    0.353553+0.000000j
|0|3|3|5|0|0|0|.>    0.353553+0.000000j
|0|3|3|6|0|0|0|.>    0.353553+0.000000j
|0|3|3|7|0|0|0|.>    0.353553+0.000000j
Uncomputed state: 
|ctrl|val_0|val_1|val_2|?>
|0|3|3|0|.>    0.353553+0.000000j
|0|3|3|1|.>    0.353553+0.000000j
|0|3|3|2|.>    0.353553+0.000000j
|0|3|3|3|.>    0.353553+0.000000j
|0|3|3|4|.>    0.353553+0.000000j
|0|3|3|5|.>    0.353553+0.000000j
|0|3|3|6|.>    0.353553+0.000000j
|0|3|3|7|.>    0.353553+0.000000j