Replacing an algorithm’s oracle¶
English · 简体中文
We first write a Bernstein–Vazirani program that does not know its function implementation, then bind a gate implementation to it. This makes the difference between “the algorithm itself is complete” and “the input oracle is still unfinished” visible.
Declare the input first¶
from oracq.algorithms.input_model.oracles import abstract_database
from oracq.algorithms.basics.oracle_algorithms import bernstein_vazirani
from oracq import unresolved
given = abstract_database("BooleanFunction", 3, 1)
opened = bernstein_vazirani(given).program()
print([item.name for item in unresolved(opened)])
assert [item.name for item in unresolved(opened)] == ["BooleanFunction"]
['BooleanFunction']
abstract_database declares an abstract database that has no implementation yet, and bernstein_vazirani assembles the algorithm on top of it. The printed list is exactly the names of the still-unbound open slots found by unresolved: the algorithm body is already complete; the only thing missing is the input implementation named BooleanFunction. The declaration provides a three-bit address and a one-bit XOR result. The algorithm assumes the function has the form f(x)=s·x XOR c; the declaration itself does not prove that premise.
Bind a gate implementation¶
from oracq.algorithms.basics.oracle_algorithms import affine_boolean_oracle
from oracq import bind, simulate
implementation = affine_boolean_oracle(3, secret=5, bias=1)
closed = bind(opened, {"BooleanFunction": implementation.operation})
assert not unresolved(closed)
state = simulate(closed)
probability = sum(abs(a)**2 for key, a in state.amplitudes.items() if key[0] == 5)
print(state.amplitudes)
print(probability)
assert abs(probability - 1) < 1e-12
{(5, 0): (-0.7071067811865471+0j), (5, 1): (0.7071067811865471+0j)}
0.9999999999999989
The gate implementation is provided by affine_boolean_oracle using ordinary reversible gates; the printed amplitudes are nonzero only on branches where the input reads 5; the ±1/√2 phase difference on the value bit comes from the affine bias, and the total probability on the second line is approximately 1. Reading the input yields 5, the secret bit string interpreted with the least significant bit first. The affine bias changes the phase but not this outcome.
Swap in a QRAM¶
The same open slot can be bound to qram_database(3,1). Use Binding(..., {"table": "truth"}) to map its resources to the entry, then supply the truth table at run time.
The gate implementation and the QRAM implementation must honor the same XOR semantics. bind checks interfaces and capabilities; the mathematical form of the function remains the application’s responsibility.