Oracle-Based Algorithms Written in Qwerty #

from qwerty import *

def deutsch(f):
  @qpu(f)
  def kernel(f: cfunc) -> bit:
    return '+' | f.phase | pm.measure

  return kernel()

@classical
def balanced(x: bit) -> bit:
  return ~x

@classical
def constant(x: bit) -> bit:
  return bit[1](0b1)

from qwerty import *

from deutsch import deutsch, \
                    balanced, \
                    constant

def naive_classical(f):
  return f(bit[1](0b0)) \
         ^ f(bit[1](0b1))

print('Balanced f:')
print('Classical: f(0) xor f(1) =',
      naive_classical(balanced))
print('Quantum: f(0) xor f(1) =',
      deutsch(balanced))

print('\nConstant f:')
print('Classical: f(0) xor f(1) =',
      naive_classical(constant))
print('Quantum: f(0) xor f(1) =',
      deutsch(constant))

from qwerty import *

def deutsch_jozsa(f):
  @qpu[N](f)
  def kernel(f: cfunc[N,1]) \
            -> bit[N]:
    return '+'[N] | f.phase \
                  | pm[N].measure

  if int(kernel()) == 0:
    return 'constant'
  else:
    return 'balanced'

@classical
def constant(x: bit[4]) -> bit:
  # f(x) = 1
  return bit[1](0b1)

@classical
def balanced(x: bit[4]) -> bit:
  # f(x) = 1 for half the inputs
  # and f(x) = 0 for the other half
  return x.xor_reduce()

from qwerty import *

from dj import deutsch_jozsa, \
               constant, balanced

def naive_classical(f, n_bits):
  answers = [0, 0]
  for i in range(2**(n_bits-1)+1):
    answer = int(f(bit[n_bits](i)))
    answers[answer] += 1

  if 0 in answers:
    return 'constant'
  else:
    return 'balanced'

print('Constant test:')
print('Classical:',
      naive_classical(constant, 4))
print('Quantum:',
      deutsch_jozsa(constant))

print('\nBalanced test:')
print('Classical:',
      naive_classical(balanced, 4))
print('Quantum:',
      deutsch_jozsa(balanced))

from qwerty import *

def bv(f):
  @qpu[N](f)
  def kernel(f: cfunc[N,1]) \
            -> bit[N]:
    return '+'[N] | f.phase \
                  | pm[N] >> std[N] \
                  | std[N].measure

  return kernel()

def get_black_box(secret_string):
  @classical[N](secret_string)
  def f(secret_string: bit[N],
        x: bit[N]) -> bit:
    return (secret_string & x) \
           .xor_reduce()

  return f

from qwerty import *
from bv import bv, get_black_box
import sys

def naive_classical(f, n_bits):
  secret_found = bit[n_bits](0b0)
  x = bit[n_bits](0b1 << (n_bits-1))
  for i in range(n_bits):
    secret_found[i] = f(x)
    x = x >> 1
  return secret_found

secret_str = \
  bit.from_str(sys.argv[1])
n_bits = len(secret_str)
black_box = get_black_box(secret_str)

print('Classical:',
      naive_classical(black_box,
                      n_bits))
print('Quantum:', bv(black_box))

import math
from qwerty import *

def period_finding(black_box):
  @qpu[M,N](black_box)
  def kernel(black_box: cfunc[M,N]) \
            -> bit[M]:
    return '+'[M] + '0'[N] \
           | black_box.xor_embed \
           | fourier[M].measure \
             + discard[N]

  result1, result2 = kernel(shots=2)
  l_over_r1 = result1.as_bin_frac()
  l_over_r2 = result2.as_bin_frac()
  r = math.lcm(l_over_r1.denominator,
               l_over_r2.denominator)
  return r

def get_black_box(n_bits_in,
                  n_bits_out,
                  n_mask_bits):
    @classical[M,N,K]
    def f(x: bit[M]) -> bit[N]:
      return bit[N-K](0b0), x[M-K:]

    return f[[n_bits_in,
              n_bits_out,
              n_mask_bits]]

import sys
from period import period_finding, \
                   get_black_box

n_bits_in = int(sys.argv[1])
n_bits_out = int(sys.argv[2])
n_masked = int(sys.argv[3])
black_box = get_black_box(n_bits_in,
                          n_bits_out,
                          n_masked)
if period_finding(black_box) \
    == 2**n_masked:
  print('success!')
else:
  print('oops...')

from qwerty import *
from simon_post import simon_post, \
                       Retry

def simon(f):
  @qpu[N](f)
  def kernel(f: cfunc[N]) -> bit[N]:
    return '+'[N] + '0'[N] \
           | f.xor_embed \
           | (std[N] >> pm[N]) \
             + id[N] \
           | std[N].measure \
             + discard[N]

  while True:
    rows = []
    while True:
      row = kernel()
      if int(row) != 0:
        rows.append(row)
        if len(rows) >= row.n_bits-1:
          break
    try:
      return simon_post(rows)
    except Retry:
      print('retrying...')
      continue

@classical
def black_box(q: bit[3]) -> bit[3]:
  return \
    (~q[0]& q[2]|q[0]&~q[2]|~q[1],
     ~q[0]&~q[2]|q[0]& q[2],
     ~q[0]&~q[2]|q[0]& q[2]|~q[1])

from qwerty import *

from simon import simon, black_box

def naive_classical(f, n_bits):
  out_to_x = {}
  for i in range(2**n_bits):
    x = bit[n_bits](i)
    out = f(x)
    if out in out_to_x:
      return x ^ out_to_x[out]
    out_to_x[out] = x

print('Classical:',
      naive_classical(black_box, 3))
print('Quantum:', simon(black_box))