Hidden-Shift problem for bent functions using the classiq platform¶

Here we implement the hidden shift algorithm for the familty of boolean bent functions.

First, make sure we have all necessary packages:

In [ ]:

%%capture
!pip install galois

%%capture !pip install galois

On the first part, we assume we know how to implement the dual of $f$, and get $s$ according to the algorithm in [1]:

In [ ]:

from functools import reduce

import numpy as np

from classiq import Model, QReg, RegisterUserInput, execute, synthesize
from classiq.builtin_functions import ArithmeticOracle, HGate
from classiq.model import Constraints

formula = "(((x1 and x2) ^ (x3 and x4)))==1"

formula_shifted = "((((x1^1) and x2) ^ (x3 and (x4)))) == 1"

NUM_VARIABLES = 4

oracle1 = ArithmeticOracle(
    expression=formula_shifted,
    definitions={f"x{i+1}": RegisterUserInput(size=1) for i in range(NUM_VARIABLES)},
    uncomputation_method="optimized",
)

oracle2 = ArithmeticOracle(
    expression=formula,
    definitions={f"x{i+1}": RegisterUserInput(size=1) for i in range(NUM_VARIABLES)},
    uncomputation_method="optimized",
)


constraints = Constraints(optimization_parameter="width")

# The model
model = Model(constraints=constraints)
# Transforming to a loop format

regs = []
for i in range(NUM_VARIABLES):
    regs.append(model.HGate(HGate())["TARGET"])

out_oracle = model.ArithmeticOracle(
    params=oracle1, in_wires={f"x{i+1}": regs[i] for i in range(NUM_VARIABLES)}
)

for i in range(NUM_VARIABLES):
    regs[i] = model.HGate(HGate(), in_wires={"TARGET": out_oracle[f"x{i+1}"]})["TARGET"]

out_oracle = model.ArithmeticOracle(
    params=oracle2, in_wires={f"x{i+1}": regs[i] for i in range(NUM_VARIABLES)}
)

for i in range(NUM_VARIABLES):
    regs[i] = model.HGate(HGate(), in_wires={"TARGET": out_oracle[f"x{i+1}"]})["TARGET"]

# Setting the Outputs
model.set_outputs({"s": reduce(QReg.concat, regs)})
model.sample()
qmod = model.get_model()

from functools import reduce import numpy as np from classiq import Model, QReg, RegisterUserInput, execute, synthesize from classiq.builtin_functions import ArithmeticOracle, HGate from classiq.model import Constraints formula = "(((x1 and x2) ^ (x3 and x4)))==1" formula_shifted = "((((x1^1) and x2) ^ (x3 and (x4)))) == 1" NUM_VARIABLES = 4 oracle1 = ArithmeticOracle( expression=formula_shifted, definitions={f"x{i+1}": RegisterUserInput(size=1) for i in range(NUM_VARIABLES)}, uncomputation_method="optimized", ) oracle2 = ArithmeticOracle( expression=formula, definitions={f"x{i+1}": RegisterUserInput(size=1) for i in range(NUM_VARIABLES)}, uncomputation_method="optimized", ) constraints = Constraints(optimization_parameter="width") # The model model = Model(constraints=constraints) # Transforming to a loop format regs = [] for i in range(NUM_VARIABLES): regs.append(model.HGate(HGate())["TARGET"]) out_oracle = model.ArithmeticOracle( params=oracle1, in_wires={f"x{i+1}": regs[i] for i in range(NUM_VARIABLES)} ) for i in range(NUM_VARIABLES): regs[i] = model.HGate(HGate(), in_wires={"TARGET": out_oracle[f"x{i+1}"]})["TARGET"] out_oracle = model.ArithmeticOracle( params=oracle2, in_wires={f"x{i+1}": regs[i] for i in range(NUM_VARIABLES)} ) for i in range(NUM_VARIABLES): regs[i] = model.HGate(HGate(), in_wires={"TARGET": out_oracle[f"x{i+1}"]})["TARGET"] # Setting the Outputs model.set_outputs({"s": reduce(QReg.concat, regs)}) model.sample() qmod = model.get_model()

In [ ]:

with open("hidden_shift_simple.qmod", "w") as f:
    f.write(qmod)

with open("hidden_shift_simple.qmod", "w") as f: f.write(qmod)

In [ ]:

from classiq import show

qprog = synthesize(qmod)
show(qprog)

from classiq import show qprog = synthesize(qmod) show(qprog)

In [ ]:

from classiq.execution import ExecutionDetails

res = execute(qprog).result()
sample_results = res[0].value
sample_results.counts_of_output("s")

from classiq.execution import ExecutionDetails res = execute(qprog).result() sample_results = res[0].value sample_results.counts_of_output("s")

More complex functions¶

We take a Maiorana-McFarland function with random permutation on the y and h function is the and operation between all the y-variables.

In [ ]:

import random

import numpy as np

NUM_VARIABLES = 16

# Define the list
my_list = list(range(NUM_VARIABLES // 2))

# Get a random permutation
random.shuffle(my_list)

# Create a permutation dict and its inverse
perm_dict = {i: my_list[i] for i in range(NUM_VARIABLES // 2)}
inverse_perm_dict = {v: k for k, v in perm_dict.items()}


def h(y):
    return " and ".join(f"{y[i]}" for i in range(NUM_VARIABLES // 2))


def h_dual(x):
    return " and ".join(f"{x[inverse_perm_dict[i]]}" for i in range(NUM_VARIABLES // 2))


def f(x, y):
    return (
        "("
        + " ^ ".join(
            f"({x[i]} and {y[perm_dict[i]]})" for i in range(NUM_VARIABLES // 2)
        )
        + ")"
        + " ^ ("
        + h(y)
        + ") == 1"
    )


def f_dual(x, y):
    return (
        "("
        + " ^ ".join(
            f"({x[inverse_perm_dict[i]]} and {y[i]})" for i in range(NUM_VARIABLES // 2)
        )
        + ")"
        + " ^ ("
        + h_dual(x)
        + ") == 1"
    )


def shifted(x, y, bits):
    x = x.copy()
    for bit in bits:
        if bit < NUM_VARIABLES >> 2:
            x[bit] = f"({x[bit]}^1)"
        else:
            bit = bit - NUM_VARIABLES // 2
            y[bit] = f"({y[bit]}^1)"
    return f(x, y)

import random import numpy as np NUM_VARIABLES = 16 # Define the list my_list = list(range(NUM_VARIABLES // 2)) # Get a random permutation random.shuffle(my_list) # Create a permutation dict and its inverse perm_dict = {i: my_list[i] for i in range(NUM_VARIABLES // 2)} inverse_perm_dict = {v: k for k, v in perm_dict.items()} def h(y): return " and ".join(f"{y[i]}" for i in range(NUM_VARIABLES // 2)) def h_dual(x): return " and ".join(f"{x[inverse_perm_dict[i]]}" for i in range(NUM_VARIABLES // 2)) def f(x, y): return ( "(" + " ^ ".join( f"({x[i]} and {y[perm_dict[i]]})" for i in range(NUM_VARIABLES // 2) ) + ")" + " ^ (" + h(y) + ") == 1" ) def f_dual(x, y): return ( "(" + " ^ ".join( f"({x[inverse_perm_dict[i]]} and {y[i]})" for i in range(NUM_VARIABLES // 2) ) + ")" + " ^ (" + h_dual(x) + ") == 1" ) def shifted(x, y, bits): x = x.copy() for bit in bits: if bit < NUM_VARIABLES >> 2: x[bit] = f"({x[bit]}^1)" else: bit = bit - NUM_VARIABLES // 2 y[bit] = f"({y[bit]}^1)" return f(x, y)

In [ ]:

x = [f"x{i+1}" for i in range(NUM_VARIABLES // 2)]
y = [f"x{i+1}" for i in range(NUM_VARIABLES // 2, NUM_VARIABLES)]

f_dual_formula = f_dual(x, y)
f_formula = f(x, y)


shifted_bits = [1, 3, 9]
g_formula = shifted(x, y, shifted_bits)

x = [f"x{i+1}" for i in range(NUM_VARIABLES // 2)] y = [f"x{i+1}" for i in range(NUM_VARIABLES // 2, NUM_VARIABLES)] f_dual_formula = f_dual(x, y) f_formula = f(x, y) shifted_bits = [1, 3, 9] g_formula = shifted(x, y, shifted_bits)

In [ ]:

print("g:", g_formula)
print("\nf:", f_formula)
print("\nf dual:", f_dual_formula)

print("g:", g_formula) print("\nf:", f_formula) print("\nf dual:", f_dual_formula)

Now create the ciruit:¶

In [ ]:

oracle1 = ArithmeticOracle(
    expression=g_formula,
    definitions={f"x{i+1}": RegisterUserInput(size=1) for i in range(NUM_VARIABLES)},
    uncomputation_method="optimized",
)

oracle2 = ArithmeticOracle(
    expression=f_dual_formula,
    definitions={f"x{i+1}": RegisterUserInput(size=1) for i in range(NUM_VARIABLES)},
    uncomputation_method="optimized",
)

constraints = Constraints(optimization_parameter="width")

# The model
model = Model(constraints=constraints)

regs = []
for i in range(NUM_VARIABLES):
    regs.append(model.HGate(HGate())["TARGET"])

out_oracle = model.ArithmeticOracle(
    params=oracle1, in_wires={f"x{i+1}": regs[i] for i in range(NUM_VARIABLES)}
)

for i in range(NUM_VARIABLES):
    regs[i] = model.HGate(HGate(), in_wires={"TARGET": out_oracle[f"x{i+1}"]})["TARGET"]

out_oracle = model.ArithmeticOracle(
    params=oracle2, in_wires={f"x{i+1}": regs[i] for i in range(NUM_VARIABLES)}
)

for i in range(NUM_VARIABLES):
    regs[i] = model.HGate(HGate(), in_wires={"TARGET": out_oracle[f"x{i+1}"]})["TARGET"]

# Setting the Outputs
model.set_outputs({"s": reduce(QReg.concat, regs)})

model.sample()
qmod = model.get_model()

oracle1 = ArithmeticOracle( expression=g_formula, definitions={f"x{i+1}": RegisterUserInput(size=1) for i in range(NUM_VARIABLES)}, uncomputation_method="optimized", ) oracle2 = ArithmeticOracle( expression=f_dual_formula, definitions={f"x{i+1}": RegisterUserInput(size=1) for i in range(NUM_VARIABLES)}, uncomputation_method="optimized", ) constraints = Constraints(optimization_parameter="width") # The model model = Model(constraints=constraints) regs = [] for i in range(NUM_VARIABLES): regs.append(model.HGate(HGate())["TARGET"]) out_oracle = model.ArithmeticOracle( params=oracle1, in_wires={f"x{i+1}": regs[i] for i in range(NUM_VARIABLES)} ) for i in range(NUM_VARIABLES): regs[i] = model.HGate(HGate(), in_wires={"TARGET": out_oracle[f"x{i+1}"]})["TARGET"] out_oracle = model.ArithmeticOracle( params=oracle2, in_wires={f"x{i+1}": regs[i] for i in range(NUM_VARIABLES)} ) for i in range(NUM_VARIABLES): regs[i] = model.HGate(HGate(), in_wires={"TARGET": out_oracle[f"x{i+1}"]})["TARGET"] # Setting the Outputs model.set_outputs({"s": reduce(QReg.concat, regs)}) model.sample() qmod = model.get_model()

In [ ]:

with open("hidden_shift_complex.qmod", "w") as f:
    f.write(qmod)

with open("hidden_shift_complex.qmod", "w") as f: f.write(qmod)

In [ ]:

qprog = synthesize(qmod)
show(qprog)

qprog = synthesize(qmod) show(qprog)

In [ ]:

from classiq.execution import ExecutionDetails

res = execute(qprog).result()
sample_results = res[0].value
sample_results.counts_of_output("s")

from classiq.execution import ExecutionDetails res = execute(qprog).result() sample_results = res[0].value sample_results.counts_of_output("s")

In [ ]:

expected_s = "".join("1" if i in shifted_bits else "0" for i in range(NUM_VARIABLES))
assert list(sample_results.counts_of_output("s").keys())[0] == expected_s

expected_s = "".join("1" if i in shifted_bits else "0" for i in range(NUM_VARIABLES)) assert list(sample_results.counts_of_output("s").keys())[0] == expected_s

And indeed we got the correct shift!

Hidden Shift without the dual function¶

We now use the second algorithm described in [2]. This algorithm only requires to implement $f$ and not its dual, however requires $O(n)$ samples from the circuit.