Deutsch–Jozsa

English · 简体中文

Category C1 · Module oracq.algorithms.basics.oracle_algorithms · Stage V1

Overview

Given a Boolean function \(f: \{0,1\}^n \to \{0,1\}\) promised to be constant or balanced (constant means \(f\) is identically 0 or identically 1; balanced means it takes 0 on half the inputs and 1 on the other half), decide which case holds with a single oracle query. The circuit exploits phase kickback: the single-bit answer is prepared in \(|-\rangle\), making the XOR oracle’s action equivalent to the phase \((-1)^{f(x)}\); after Hadamard interference on the uniformly superposed input, the input of a constant function collapses entirely back to \(|0^n\rangle\), while the readout of a balanced function is necessarily nonzero. Classical deterministic decision requires \(2^{n-1}+1\) queries in the worst case.

Interface and input model

deutsch_jozsa(function: XorDatabase)

API entry point: deutsch_jozsa

• function: a single-result-bit XOR database (input model FO: the Boolean function’s truth table); data_width must be 1, otherwise ValidationError is raised at generation time. XorDatabase supports three-layer construction: gate_database (gate-level truth table), qram_database (QRAM lookup), and abstract_database (an open declaration, bound later).

Returns an Operation with registers input: Bits(address_width) and answer: Bits(1). Module attributes:

Attribute	Meaning
algorithm	"deutsch_jozsa"
readout_register	"input" (the decision reads only input; answer is not read)
validation_stage	"paradigm" (witness-level annotation)

Implementation notes

The generation sequence is: X then H on answer (preparing \(|-\rangle\)) → H on all of input (uniform superposition) → the oracle resource invoked with the function prefix via invoke → H on all of input. The oracle is kept as a module call (a resource binding with the function__ prefix) and is not expanded during generation or serialization. The constant/balanced promise is the caller’s responsibility: an all-zero input readout indicates constant, a nonzero one indicates balanced; no guarantee is made about the output for functions that do not satisfy the promise.

Applicability boundary: only XOR databases with data_width == 1 are accepted; the phase-kickback route requires the answer’s initial state to be preparable as \(|-\rangle\), which is handled inside the circuit — the caller need not (and should not) preprocess answer.

Validation approach

Category C1 (exact discrete semantics; acceptance criterion in ../development/validation-plan.md §2): the output distribution must equal the exact construction of the promised case pointwise. Three layers of evidence:

• Structure: tests/core/test_algorithm_expansion.py:AlgorithmExpansionTests.test_legacy_imports_reference_canonical_objects (consistency of the module’s canonical objects with the historical import names, matrix criterion).

• Numerical: this algorithm has no dedicated DJ numerical test (matrix criterion), but the Bernstein–Vazirani witness AlgorithmExpansionTests.test_bernstein_vazirani_recovers_secret_with_affine_bias runs exactly the same circuit — bernstein_vazirani directly wraps the product of deutsch_jozsa, cross-checked distribution by distribution on all 3-bit secret strings with places = 10, so DJ’s interference structure is covered indirectly.

• Binding: tests/core has no independent binding witness (matrix criterion is —). The dj_gate / dj_qram cases in applications/catalog.py bind the open declaration BooleanFunction to a gate-level truth table and to QRAM respectively at the L3 layer, as a catalog demonstration of the binding path.

Known gaps and planned stages

No known gaps (the gap column of the validation matrix is —); stage V1.

Related links

• Same module: Bernstein–Vazirani secret-string readout, Simon sampling

• Source: src/oracq/algorithms/basics/oracle_algorithms.py

• API reference: Oracle query algorithms

• Validation matrix: Validation coverage matrix

Numerical validation

Paper-grade numerical validation script: tests/verification/verify_oracles.py (group C cases), artifact out/verification/oracles.json.

Experimental design: widths 2–5 bit, with five promised functions per width — constant 0, constant 1, balanced parity (\(s\cdot x\) with all-ones \(s\)), balanced MSB, and a balanced threshold function (nonlinear); all oracles are gate_database truth tables. The decision metric is \(P(\mathrm{input}=0)\): it must be exactly 1 for the constant cases and exactly 0 for the balanced cases; the constant and linear-balanced families have closed-form final states \((-1)^c|0^n\rangle|-\rangle\) / \(|s\rangle|-\rangle\), which additionally get a phase-sensitive amplitude-by-amplitude cross-check. There are also end-to-end cases with a BooleanNetwork-compiled oracle (parity3 / const3): after the network is compiled via operation() and wrapped in the XOR database interface, the 16 branches of net.evaluate are first exhaustively enumerated amplitude by amplitude under superposition, then the DJ decision is run (see the numerical-validation section of Boolean networks). Backend paths: reference, rir-pysparq, originir-ext.

Case	Scale	Path	Metric value
dj-decision-w2	2 bit, 5 functions	reference, rir-pysparq, originir-ext	p_zero_max_error = 7.8e-16, decision_errors = 0, closed-form max_error = 2.2e-16
dj-decision-w3	3 bit, 5 functions	same as above	p_zero_max_error = 1.1e-15, decision_errors = 0, closed-form max_error = 3.3e-16
dj-decision-w4	4 bit, 5 functions	same as above	p_zero_max_error = 1.4e-15, decision_errors = 0, closed-form max_error = 4.4e-16
dj-decision-w5	5 bit, 5 functions	same as above	p_zero_max_error = 1.8e-15, decision_errors = 0, closed-form max_error = 5.6e-16
dj-boolean-network-parity3	3 bit balanced (network-compiled)	rir-pysparq, originir-ext	max_error = 8.3e-17, p_zero_error = 0.0
dj-boolean-network-const3	3 bit constant (network-compiled)	rir-pysparq, originir-ext	max_error = 8.3e-17, p_zero_error = 1.1e-15

Reproduction command:

PYTHONPATH=src /path/to/backend/python tests/verification/verify_oracles.py

Artifact path: out/verification/oracles.json.