Quantum Oracles

A quantum oracle is a declared information-access interface: a coherent operation, family of operations, or channel through which an algorithm may interrogate an instance. It is not a magic gate, a circuit implementation, or a promise that one query is physically cheap. Even the phrase “standard oracle” is ambiguous until the domain, register encoding, target action, promises, phase representative, and optional access capabilities have been fixed.

This page owns the specification and comparison of oracle interfaces. It explains what one query means, when two forms are equivalent, which information a phase interface discards, and how to separate query count from construction and use cost. It stops before algorithm-specific correctness and lower bounds, general reversible synthesis, device realization, or an end-to-end advantage verdict.

Required background. Reversible Computation supplies full-space embeddings, permutation-unitary semantics, workspace, garbage, and uncomputation. Phase Kickback supplies the clean bit- and value-to-phase derivations, character-state conditions, and target-return tests used here without rederivation.

Oracle Interfaces as Information-Access Contracts

An oracle problem begins with an instance family, not a gate symbol. A Boolean predicate, an indexed table, a permutation, a unitary, and a channel expose different kinds of information even if they are all labeled with the letter $O$. The interface must answer four separate questions:

• Which instance $f$ or operator $U$ is hidden, and what promise restricts it?
• On which complete Hilbert space does a query act, including targets and workspace?
• Which calls are supplied: forward, inverse, controlled, powered, or coherently indexed family access?
• What output and comparison are intended after the queries?

The mathematical action and the supplied capability are distinct. Knowing that an operator has an inverse does not mean an opaque device supplies that inverse at unit query cost. Writing a block-diagonal controlled operator does not show that a phase-indefinite channel can be placed coherently in one branch. Calling a table lookup one query does not price memory construction, routing, error correction, or readout.

The Circuit Model owns generic registers, composition, output, and resource syntax. Here those ingredients are specialized to information access. A valid oracle claim must remain meaningful if another reader reconstructs the full map, repeats the declared query experiment, and checks the same acceptance metric.

The Ten-Field Oracle Record

Complete this record before comparing oracle forms or reporting a query advantage. Every field must contain a value or a reasoned N/A; an omitted capability is not silently available.

1. Oracle task and licensed claim — State the access question and the strongest conclusion that the evidence may support.
2. Instance family, domains, codomains, and promises — Name the hidden instance family, its mathematical input and output sets, and every promise.
3. Registers, dimensions, order, and encodings — Name all query, target, work, reference, and classical registers; fix tensor order, dimensions, basis order, and bit significance.
4. Full-space oracle action and phase representative — Give the action on every basis state or the complete channel, and fix an exact unitary representative whenever relative control can expose its phase.
5. Forward, inverse, controlled, powered, and family access — Record each capability independently, including whether it is primitive, constructed, or unavailable.
6. Input state, workspace, garbage, and cleanup — State preparation and clean-register promises, identify residual records, and specify what must be restored.
7. Conversion or reduction, output, measurement, and postprocessing — Give any interface conversion with its assumptions and overhead, then state the requested output and how it is extracted.
8. Query convention, hidden costs, and fair comparator — Define one query, list excluded construction and use costs, and give the comparator an explicitly matched information contract.
9. Verification data, metric, tolerance, uncertainty, and reproducibility — Fix analytic references, numerical representation, comparison space, metric, tolerance, uncertainty type, runtime, tensor order, and stable recipe identity.
10. Conclusion, stopping point, and canonical handoff — Report pass or fail, stop at the evidence boundary, and route algorithms, compilation, hardware, or broader evidence claims to their owners.

A filled record prevents a query from being silently reclassified as an elementary gate, a partial promised map from being treated as a full unitary, or a channel-level equivalence from being promoted to exact controlled-unitary equality.

Domains, Encodings, and Promise Layers

For a function $f:X\to Y$, the sets $X$ and $Y$ do not by themselves determine a quantum query. One must choose Hilbert-space registers, basis encodings, and a complete action outside any clean-input slice. A rule stated only as

$$|x\rangle|0\rangle \longmapsto |x\rangle|f(x)\rangle$$

specifies an isometry on one target subspace. It does not say what happens for a nonzero target and therefore is not yet a full unitary oracle.

Four promise layers should remain separate:

1. the unknown instance lies in a declared family $f\in\mathcal F_{\mathrm{promise}}$;
2. query states may be restricted to a subspace with projector $\Pi_D$;
3. target and work registers may be promised clean; and
4. the surrounding algorithm has an output and success promise.

The first restricts which black box is chosen. The second restricts where it will be queried. The third is an input-state resource. The fourth describes the task rather than the query map. Moving a condition from one layer to another can change both correctness and cost.

Suppose two full unitaries satisfy

$$(\Pi_D\otimes I)U_f(\Pi_D\otimes I) = (\Pi_D\otimes I)V_f(\Pi_D\otimes I).$$

They are interchangeable only for an evolution proved to remain in the promised subspace at every query. A coherent amplitude outside $D$ can encounter different extensions and later interfere with valid branches. Equality of a partial truth table is therefore not full-unitary equality.

An exact phase representative is another part of the encoding. Uncontrolled channels generated by $U$ and $e^{i\gamma}U$ coincide, while their controlled representatives differ. A record that may later request controlled access must fix that phase information at the interface boundary.

Reversible Bit and Value Oracles

Let the query-label register use basis $|x\rangle$, and let an $M$-level target encode the additive group $\mathbb Z_M$. The positive modular-addition interface is

$$O_f^{(+)} = \sum_{x\in X} |x\rangle\langle x|\otimes T_{f(x)}, \qquad T_a|y\rangle = |y+a\bmod M\rangle.$$

Once the ambient registers and every target basis state are declared, this is unitary because each $T_a$ is a permutation. Its inverse subtracts the value:

$$O_f^{(-)} |x\rangle|y\rangle = |x\rangle|y-f(x)\bmod M\rangle.$$

Modular addition is not generally self-inverse. The equality

$$O_f^{(+)}=O_f^{(-)}$$

holds exactly when

$$2f(x)=0\pmod M \quad \text{for every }x.$$

For a bit-string value, the usual interface instead uses bitwise XOR:

$$B_f|x\rangle|y\rangle = |x\rangle |y\mathbin{\oplus}f(x)\rangle, \qquad B_f^\dagger=B_f.$$

The involution follows because XORing the same string twice cancels, for every target $y$, not merely for $y=0$. This exact difference between XOR and modular addition matters whenever inverse access is counted.

Other reversible interfaces include in-place permutation access,

$$U_\pi|x\rangle=|\pi(x)\rangle,$$

and indexed lookup into a value target. Reversible Computation owns how an ordinary many-to-one function is embedded, how ancillas and garbage are managed, and how an explicit circuit is uncomputed. The oracle contract begins from that construction when it is known, or records construction as absent when only black-box access is supplied.

Phase, Character, and Reflection Oracles

Set

$$\omega_M=e^{2\pi i/M}.$$

For a fixed character label $k$, the phase interface

$$P_{f,k}|x\rangle = \omega_M^{k f(x)}|x\rangle$$

retains only the character of the value. It distinguishes two values $a,b\in\mathbb Z_M$ exactly when

$$k(a-b)\ne0\pmod M.$$

The map $a\mapsto\omega_M^{ka}$ is injective on all values precisely when $\gcd(k,M)=1$. Otherwise its kernel identifies several values, so one fixed character does not carry the complete value.

For Boolean $f$, the phase oracle is a reflection:

$$P_f = \sum_x(-1)^{f(x)} |x\rangle\langle x| = I-2\Pi_{f=1}.$$

This identity specifies an interface. Grover Search owns the marked-set promise, two-reflection rotation, stopping rule, and optimal search-query bound.

A stronger coherent character-family interface keeps $k$ quantum:

$$D_f|x\rangle|k\rangle = \omega_M^{k f(x)} |x\rangle|k\rangle.$$

Using the explicit positive-exponent Fourier convention

$$F_M|y\rangle = \frac1{\sqrt M} \sum_{k=0}^{M-1} \omega_M^{ky}|k\rangle,$$

the value oracle obeys

$$O_f^{(+)} = (I\otimes F_M^\dagger) D_f (I\otimes F_M).$$

This reduction uses one coherent-family query plus one forward and one inverse finite Fourier transform. It is not a reduction from one fixed $P_{f,k}$. Quantum Fourier Transform owns transform signs, factorization, bit order, exact and approximate circuits, swaps, and gate counts.

Unitary and channel oracles form further interface classes. A unitary query exposes coherent amplitudes and phases relative to a fixed representative. A channel query exposes only the input–output channel and may erase the global phase information needed for coherent control. Sparse-Hamiltonian, block-encoding, state-preparation, QRAM, and noisy-channel interfaces require their own specialist contracts; the same word “oracle” does not make them interchangeable.

Inverse, Controlled, Powered, and Family Access

For a general unitary oracle $U$, the following are separate capabilities:

• a forward call to $U$;
• an inverse call to $U^\dagger$;
• a phase-fixed controlled call $C(U)$;
• a primitive call to $U^r$ or to a family of powers; and
• a coherent family call indexed by a quantum label.

A known circuit may allow one to reverse its gates, add controls gate by gate, or repeat it. Each construction inherits the circuit’s ancillas, approximation, routing, and phase convention. An opaque forward device need not supply any of those constructions at one-query cost.

The controlled operator

$$C_1(U) = |0\rangle\langle0|\otimes I + |1\rangle\langle1|\otimes U$$

is a well-defined matrix after an exact representative of $U$ is fixed. That algebra does not prove that a black-box channel can be controlized. Controlled Operations owns the general projector-block semantics, branch-relative phase, and unknown-operation controlization obstruction. The oracle record states which phase reference or extra physical structure, if any, is actually supplied.

Powered access also changes the resource model. Calling $U^{2^j}$ one query is stronger than synthesizing it from $2^j$ calls to $U$. Quantum Phase Estimation owns the phase-estimation circuit, precision, decoder, success probability, and coherent-time cost. This page owns only the declaration of the powered-access capability on which such a cost statement rests.

Equivalences Require Declared Capabilities

For Boolean $f$, Phase Kickback proves the licensed clean conversion

$$B_f \left( |\psi\rangle|-\rangle \right) = P_f|\psi\rangle|-\rangle.$$

The minus target is an eigenstate resource, and exact target return is part of the result. One bit query therefore realizes one phase query on the data under this preparation contract.

The reverse direction requires more than plain phase access. Define the exact target-controlled representative

$$C_y(P_f) = I_X\otimes|0\rangle\langle0|_y + P_f\otimes|1\rangle\langle1|_y.$$

Then

$$B_f = (I_X\otimes H_y) C_y(P_f) (I_X\otimes H_y).$$

The reduction costs one declared controlled-phase query and two Hadamards. It cannot begin from an uncontrolled phase-channel interface, because

$$P_{1\mathbin{\oplus}f} = -P_f.$$

The two exact matrices differ, their uncontrolled channels coincide, and their controlled representatives differ by a relative branch phase. Thus “bit and phase oracles are equivalent” is defensible only after the allowed control and phase-reference capabilities have been stated.

The coherent-family reduction for $\mathbb Z_M$ has the same lesson. Access to all $k$ in superposition can recover value addition through Fourier conjugation, while a fixed character may have a nontrivial kernel. An equality of abstract matrices is not an equality of query models unless every added transform, control, inverse, state preparation, and approximation is included.

Workspace, Approximation, and Verification

A clean oracle returns all work registers required by its interface. A dirty implementation may act as

$$A_f|x\rangle|0\rangle_W|0\rangle_Y = |x\rangle|w_x\rangle_W|f(x)\rangle_Y.$$

If a later step ignores $W$, data coherences are weighted by overlaps such as $\langle w_{x'}|w_x\rangle$. Orthogonal workspace can erase interference even when every basis-label output is correct. Generic embedding and compute–copy–uncompute remain with Reversible Computation; the oracle record must say whether a supplied query already includes cleanup.

Exact inverse access and a mathematical inverse should not be conflated. If the implementation is known, one may compute, use the intended output, and apply the actual inverse. If only a forward black box is supplied, an inverse query is unavailable unless it is independently declared or constructible from allowed forward calls.

Approximate queries need a metric on a declared space. If each call satisfies the operator-norm bound

$$\|\widetilde O_f-O_f\| \leq \epsilon,$$

then for an interleaved $Q$-query unitary computation, a telescoping argument gives

$$\|\widetilde\psi_Q-\psi_Q\| \leq Q\epsilon.$$

This conservative deterministic bound is neither a shot-noise interval nor a stochastic hardware-noise model. It applies to the specified comparison space; a promise-subspace bound cannot silently become a full-space guarantee.

Verification should cover more than a classical truth table. Depending on the interface, useful tests include:

• complete basis action and inverse or involution;
• relative phases on superpositions;
• agreement on and leakage from a promised subspace;
• target and workspace return;
• reduced-state purity or correlations;
• a controlled-reference test when phase representatives matter; and
• a stable numerical recipe with basis order, runtime, metric, tolerance, and uncertainty type.

Query Accounting and Fair Classical Comparison

An oracle query is one use of the interface named in the theorem or audit. It is not automatically one logical gate, one memory access, or one unit of physical time. A useful ledger separates

$$\begin{aligned} T_{\mathrm{end}} ={}& Q C_{\mathrm{query}} +C_{\mathrm{prepare}} +C_{\mathrm{between}}\\ &+C_{\mathrm{readout}} +C_{\mathrm{classical}}. \end{aligned}$$

A query separation fixes only $Q$. The cost per query may include arithmetic, memory, reversible workspace, synthesis, routing, error correction, or long-time evolution. Construction and loading may be paid once, per instance, per update, or per run; the amortization rule must be stated.

A fair classical comparison fixes the same underlying problem promise and demands an equivalently useful output at matched accuracy and success probability. Classical access need not be a coherent quantum unitary, but it must expose the corresponding function information under an explicit query convention. Neither side should receive an unpriced precomputed structure, stronger promise, shorter output, or weaker error requirement.

Classical Information Review owns the general representation, construction, output, accuracy, and total-cost comparator. Algorithmic Primitives owns how a declared access interface composes with phase, interference, amplification, spectral processing, and readout. This page licenses only the oracle-specific information and capability match.

Worked Audit: Boolean Complement Ambiguity

Consider the two-function promise $h\in\{f,g\}$ on data basis $00,01,10,11$, with

$$f=(0,1,1,0), \qquad g=1\mathbin{\oplus}f=(1,0,0,1).$$

The complete interface record is:

1. Oracle task and licensed claim — Compare bit and phase access for the promised pair $\{f,g\}$; determine exactly what uncontrolled phase access loses and what extra capability restores a value bit. Passing licenses only these ideal interface statements, not an algorithmic speedup.
2. Instance family, domains, codomains, and promises — The unknown instance is $h\in\{f,g\}$, with domain $\{0,1\}^2$, codomain $\{0,1\}$, and no query-domain restriction. The bit target is a qubit; controlled-phase access is a separate model, not part of the phase-only promise.
3. Registers, dimensions, order, and encodings — Use data order $(x_1,x_0)$ and optional target $y$, with full tensor order $(x_1,x_0,y)$, big-endian data basis $00,01,10,11$, and target basis $0,1$.
4. Full-space oracle action and phase representative — The bit form is $B_h|x\rangle|y\rangle=|x\rangle|y\oplus h(x)\rangle$. The phase forms are $P_f=\operatorname{diag}(1,-1,-1,1)$ and $P_g=\operatorname{diag}(-1,1,1,-1)=-P_f$; these exact representatives are fixed before control.
5. Forward, inverse, controlled, powered, and family access — Model A supplies one forward bit query, with $B_h^\dagger=B_h$. Model B supplies only uncontrolled $P_h$. Model C separately supplies exact $C_y(P_h)$. Powered and character-family access are N/A: neither is part of this promised interface.
6. Input state, workspace, garbage, and cleanup — For the bit comparison, prepare $|++\rangle|0\rangle$. There is no workspace or garbage. For the phase-channel comparison, allow arbitrary data density operator $\rho$.
7. Conversion or reduction, output, measurement, and postprocessing — The uncontrolled phase channels coincide for every $\rho$. The two bit outputs on the declared pure input are orthogonal. Exact controlled-phase access, plus $H_y$ before and after, reconstructs $B_h$; plain $P_h$ access does not.
8. Query convention, hidden costs, and fair comparator — Count one call to whichever interface is explicitly supplied. The controlled reduction also uses two $H$ gates. Oracle construction, controlization, synthesis, routing, and hardware cost are N/A, meaning that this ideal audit neither supplies nor prices them. Compare classical and quantum procedures only after fixing which underlying function information each receives.
9. Verification data, metric, tolerance, uncertainty, and reproducibility — The normative results are zero phase-channel distance, bit-output overlap zero, normalized bit-output trace distance one, bit-oracle unitarity and involution, and the exact Hadamard-sandwich identity. Use the embedded binary64 dense record below with absolute tolerance $2\times10^{-14}$. Sampling uncertainty is N/A because this is a deterministic dense calculation.
10. Conclusion, stopping point, and canonical handoff — Pass: uncontrolled phase access identifies $f$ and its complement only up to a global sign, whereas bit access distinguishes them; controlled phase restores a reference only when supplied. Stop before the unknown-control proof, named algorithms, lower bounds, implementation, or advantage claims.

On $|++\rangle|0\rangle$, the bit outputs are

$$|\Psi_f\rangle = \frac12\bigl( |00\rangle|0\rangle +|01\rangle|1\rangle +|10\rangle|1\rangle +|11\rangle|0\rangle \bigr),$$ $$|\Psi_g\rangle = \frac12\bigl( |00\rangle|1\rangle +|01\rangle|0\rangle +|10\rangle|0\rangle +|11\rangle|1\rangle \bigr),$$

with $\langle\Psi_f|\Psi_g\rangle=0$, so their normalized pure-state trace distance is one. Yet for every $\rho$,

$$P_g\rho P_g^\dagger=P_f\rho P_f^\dagger.$$

After $q$ ordinary phase queries, the two ideal state vectors differ only by the global factor $(-1)^q$. The distinction becomes observable only when a declared reference branch makes that representative phase relative, as in exact controlled access.

The following record is normative. Decode its HTML entities, normalize line endings to LF, and retain exactly one final LF before hashing. Its SHA-256 is 031F20FD3361D99BC05B9CC9DB325E4E8024DFA50D319CF19C6E36FAE3BF7569.

artifact=quantum-oracles-boolean-complement-v1
runtime=Node.js v26.4.0
precision=IEEE-754 binary64
tensor=x1,x0,y
data_basis=00,01,10,11
f_table=0,1,1,0
g_table=1,0,0,1
relation=g=1 xor f
bit_oracle=|x>|y> -> |x>|y xor f(x)>
phase_f=diag(1,-1,-1,1)
phase_g=-phase_f
construction=dense real bit permutations, phase diagonals, and y-controlled phase
normative_uncontrolled_phase_channel_distance=0
normative_bit_output_overlap=0
normative_bit_output_trace_distance=1
plain_phase_to_bit=not licensed without controlled phase access
observed_bit_unitarity_max_entry_error=0
observed_bit_involution_max_entry_error=0
observed_controlled_phase_to_bit_max_entry_error<3e-16
acceptance_absolute_error<=2e-14
uncertainty=N/A deterministic dense audit

Worked Audit: A Coherent Four-Entry Lookup

Let the two-bit lookup table be

$$d=(3,1,2,0),$$

so $d(00)=11$, $d(01)=01$, $d(10)=10$, and $d(11)=00$. Declare the clean bitwise-XOR value oracle

$$O_d|x\rangle|y\rangle = |x\rangle|y\mathbin{\oplus}d(x)\rangle.$$

The complete interface record is:

1. Oracle task and licensed claim — Verify coherent lookup, its exact input–output correlations, both reduced states, one-shot readout, and uncomputation. Passing licenses this ideal interface behavior only; it does not license bulk classical readout, table construction, or speedup.
2. Instance family, domains, codomains, and promises — Use the fixed map $d:\{0,1\}^2\to\{0,1\}^2$ with table $(3,1,2,0)$ and no query-domain promise. The target is promised clean in $|00\rangle$ for the tested input.
3. Registers, dimensions, order, and encodings — Use four qubits in order $(x_1,x_0,y_1,y_0)$, big-endian two-bit encodings, and ascending basis order on each register.
4. Full-space oracle action and phase representative — Use the exact sixteen-dimensional XOR permutation above on every target value. Its phase representative has all nonzero matrix entries $+1$.
5. Forward, inverse, controlled, powered, and family access — One forward query is supplied and $O_d^\dagger=O_d$ mathematically, so the same supplied interface can be called a second time to uncompute. Controlled, powered, and character-family interfaces are N/A because they are not supplied.
6. Input state, workspace, garbage, and cleanup — Prepare $|++\rangle_X|00\rangle_Y$ with two $H$ gates. There is no additional workspace or garbage. A second query returns the complete state to that input.
7. Conversion or reduction, output, measurement, and postprocessing — One query produces the four correlated rows below. Both marginals are $I_4/4$, with purity $1/4$ and entropy two bits. One joint computational-basis shot returns one table row with probability $1/4$; it does not print the table.
8. Query convention, hidden costs, and fair comparator — Count two input $H$ gates and one abstract forward query for lookup; count a second forward query only for the round-trip cleanup test. Table loading, memory, query synthesis, depth, routing, and physical cost are N/A, meaning they are outside this ideal interface audit. A comparator must receive an explicitly matched lookup interface and output obligation.
9. Verification data, metric, tolerance, uncertainty, and reproducibility — The exact state, marginals, purity, base-two entropy, row probabilities, involution, and returned input are normative. Use the embedded binary64 dense record below with absolute tolerance $2\times10^{-14}$. Sampling uncertainty is N/A for the deterministic state-vector calculation.
10. Conclusion, stopping point, and canonical handoff — Pass: the clean query creates coherent correlations and is exactly uncomputed by a second call, while measurement returns only one row per shot. Stop before memory construction, QRAM, algorithmic advantage, noise, or hardware evidence.

The exact post-query state is

$$O_d|++\rangle|00\rangle = \frac12\bigl( |00\rangle|11\rangle +|01\rangle|01\rangle +|10\rangle|10\rangle +|11\rangle|00\rangle \bigr).$$

Because $d$ is a permutation, this is maximally entangled across the two two-qubit registers:

$$\rho_X=\rho_Y=\frac{I_4}{4}, \qquad \operatorname{Tr}(\rho_X^2) = \operatorname{Tr}(\rho_Y^2) = \frac14,$$ $$S(\rho_X)=S(\rho_Y)=2\ \text{bits}.$$

Thus all four joint rows have probability $1/4$, while either register alone is maximally mixed. The second query acts on the full coherent state and returns $|++\rangle_X|00\rangle_Y$; measuring first would instead destroy that round-trip state.

The following record uses the same entity-decoding, LF-normalization, and single-final-LF rule. Its SHA-256 is 67F998A98837A7B8532E525CC191968A6F41E60402568CF8CEEC826872E1AAF6.

artifact=quantum-oracles-coherent-lookup-d3120-v1
runtime=Node.js v26.4.0
precision=IEEE-754 binary64
tensor=x1,x0,y1,y0
input=|++> tensor |00>
lookup_table=3,1,2,0
oracle=|x>|y> -> |x>|y xor d(x)>
output_pairs=00:11,01:01,10:10,11:00
nonzero_amplitude=0.5
construction=dense real XOR permutation on the declared input
normative_input_marginal=I4/4
normative_output_marginal=I4/4
normative_marginal_purity=0.25
normative_marginal_entropy_bits=2
normative_joint_row_probability=0.25 each
normative_rows_per_joint_shot=1
observed_oracle_unitarity_max_entry_error=0
observed_oracle_involution_max_entry_error=0
observed_marginal_max_entry_error=0
observed_uncompute_state_residual=0
acceptance_absolute_error<=2e-14
uncertainty=N/A deterministic dense audit

Common Failure Modes and Ownership Boundaries

Treating a partial map as a unitary. Values listed only on a promise domain do not determine the ambient action. Supply a full reversible extension, or state precisely why every licensed evolution remains inside the promised subspace.

Reporting only the clean-target slice. The rule $|x\rangle|0\rangle\mapsto|x\rangle|f(x)\rangle$ does not specify an oracle on arbitrary target states. State the full XOR, modular-addition, or other target action.

Moving an involution claim between group laws. Bitwise XOR value access is always self-inverse. Modular addition is self-inverse only when every added value has order at most two.

Calling bit and phase access interchangeable. The clean bit-to-phase reduction uses a suitable target eigenstate. The reverse Boolean reduction requires an exact controlled phase representative; a plain uncontrolled channel does not supply one.

Promoting optional capabilities silently. Forward access does not automatically include $U^\dagger$, $C(U)$, a coherent family, or a powered-query primitive. Record each capability separately and debit any reduction used to construct it.

Ignoring character kernels or dirty work. A fixed character can erase value distinctions, and residual garbage can erase useful interference. State the character kernel, target return, workspace state, and cleanup obligation.

Equating one query with one gate. Query count, synthesis cost, coherent time, memory construction, routing, readout, and classical postprocessing are different currencies. A query separation alone is not an end-to-end advantage claim.

Calling coherent lookup bulk readout. A superposition query can create correlations across every table row, but one joint computational-basis shot returns one row. Extracting an entire classical table remains an output task that must be counted.

Reversible Computation owns finite reversible embeddings, complete permutations, workspace, garbage, and generic compute–copy–uncompute. Controlled Operations owns projector and block semantics, relative branch phases, exact control representatives, and the obstruction to universally controlling an unknown channel oracle. Phase Kickback owns eigenstate and character-state transduction, clean conversions, target return, and phase-sensitive verification.

Quantum Fourier Transform owns transform conventions, factorization, approximation, bit reversal, and logical counts. Algorithmic Primitives owns the composition of a declared interface with interference and readout. Quantum Phase Estimation owns powered eigenphase accumulation, decoding, precision, aliasing, success probability, and coherent-time cost; Grover Search owns its marked-set promise, reflection rotation, stopping rule, and optimal search-query bound.

Amplitude Amplification begins from a licensed coherent preparation and inverse, good-subspace reflection, reference-state reflection, and verifier, then owns the general invariant-plane rotation, schedule regimes, component scaling, and access limitations.

Amplitude Estimation additionally requires a precise controlled representative of that iterate and licensed powered access; writing $Q$ does not supply either capability.

Classical Information Review owns matched representation, input, output, accuracy, construction, and total-cost comparison. Query Complexity owns fixed-cap classical and quantum query measures, reductions, lower-bound methods, composition theorems under their hypotheses, and proved matched-access separations after this page fixes the interface. Quantum Complexity Classes owns relativization and formal complexity-class claims, while Claims, Hype, and Evidence Standards owns broader evidence and end-to-end advantage claims.

Deutsch–Jozsa Algorithm begins from the complete Boolean XOR interface and owns its constant-versus-balanced promise, modern one-query circuit, exact correctness proof, and matched classical comparison.

Bernstein–Vazirani Algorithm begins from the same complete Boolean XOR interface and owns hidden linear-word recovery, its one-query character proof, and the matched classical $n$-query comparison.

Simon’s Algorithm begins from a complete many-bit XOR value interface and owns the unique hidden XOR-period promise, coset-state Fourier sampling, binary-rank recovery and verification, and the matched exponential query separation.

Sparse Hamiltonian access, state preparation, QRAM, channel models, synthesis, hardware, and implementation evidence belong to their specialist owners; none is interchangeable with an undeclared oracle interface.

Exercises

1. Extend a Promised Oracle

A Boolean function is specified only on $D=\{0,1,2\}\subset\{0,1,2,3\}$. Construct two full XOR-oracle extensions with $f_0(3)=0$ and $f_1(3)=1$. Prove that they agree on the promised query subspace but are not the same full unitary.

Solution

Let $f_D:D\to\{0,1\}$ be the specified function and define

$$f_b(x)= \begin{cases} f_D(x),&x\in D,\\ b,&x=3, \end{cases} \qquad b\in\{0,1\}.$$

Each rule

$$B_{f_b}|x\rangle|y\rangle = |x\rangle|y\oplus f_b(x)\rangle$$

is a full unitary because it permutes the complete computational basis. If $\Pi_D=\sum_{x\in D}|x\rangle\langle x|$, then

$$(\Pi_D\otimes I)B_{f_0}(\Pi_D\otimes I) = (\Pi_D\otimes I)B_{f_1}(\Pi_D\otimes I),$$

since the two extensions agree for every $x\in D$. Outside that subspace,

$$B_{f_0}|3\rangle|0\rangle=|3\rangle|0\rangle, \qquad B_{f_1}|3\rangle|0\rangle=|3\rangle|1\rangle.$$

These outputs are orthogonal. Agreement under the promise therefore does not imply equality of the ambient unitaries.

2. Derive the Inverse and Involution Condition

For modular-addition access to $f:X\to\mathbb Z_M$, derive the inverse and determine exactly when the oracle is self-inverse. Contrast the result with a bitwise-XOR value oracle.

Solution

Applying addition and then subtraction gives

$$O_f^{(-)}O_f^{(+)}|x\rangle|y\rangle = |x\rangle|(y+f(x))-f(x)\bmod M\rangle = |x\rangle|y\rangle.$$

Thus

$$\left(O_f^{(+)}\right)^\dagger = O_f^{(-)}, \qquad O_f^{(-)}|x\rangle|y\rangle = |x\rangle|y-f(x)\bmod M\rangle.$$

The two actions are equal exactly when $y+f(x)=y-f(x)\pmod M$ for every $x,y$, equivalently

$$2f(x)=0\pmod M$$

for every $x$. Necessity follows by cancelling $y$; sufficiency follows by replacing $-f(x)$ with $f(x)$ in every target basis state. By contrast, bitwise XOR satisfies $(y\oplus f(x))\oplus f(x)=y$ for every bit string, so its value oracle is always self-inverse.

3. Diagnose Boolean Complement Ambiguity

For Boolean $f$ and $g=1\oplus f$, distinguish equality of exact unitary representatives, equality up to global phase, and equality of uncontrolled channels. Then verify the bit-output distinction in the first audit.

Solution

On each data basis state,

$$P_g|x\rangle = (-1)^{1\oplus f(x)}|x\rangle = -(-1)^{f(x)}|x\rangle,$$

so $P_g=-P_f$. The exact matrices are unequal, but they represent the same operation up to a global phase. Consequently their uncontrolled channels are identical:

$$P_g\rho P_g^\dagger = (-P_f)\rho(-P_f^\dagger) = P_f\rho P_f^\dagger.$$

For the audit input, the support of $|\Psi_f\rangle$ is the four basis vectors $000,011,101,110$, whereas the support of $|\Psi_g\rangle$ is $001,010,100,111$. The supports are disjoint, so $\langle\Psi_f|\Psi_g\rangle=0$ and the normalized pure-state trace distance is

$$\sqrt{1-|\langle\Psi_f|\Psi_g\rangle|^2}=1.$$

Thus bit access distinguishes the pair in this test, while uncontrolled phase-channel access does not.

4. Find a Character Kernel

For $M=12$ and $k=8$, find the kernel of $a\mapsto\omega_{12}^{8a}$ and determine what value information one fixed character retains.

Solution

The kernel condition is

$$8a=0\pmod{12}.$$

Since $\gcd(8,12)=4$, this is equivalent to $a=0\pmod 3$. Hence

$$\ker\chi_8=\{0,3,6,9\}.$$

Moreover,

$$\omega_{12}^{8a} = \exp\left(\frac{2\pi i\,8a}{12}\right) = \exp\left(\frac{2\pi i\,2a}{3}\right),$$

so the phase depends only on $a$ modulo three. Values separated by an element of the four-element kernel are indistinguishable; one fixed character therefore cannot recover a general value in $\mathbb Z_{12}$. Coherent family access is stronger because a supplied register $k$ can retain and compare multiple characters rather than fixing this noninjective one.

5. License a Controlled Phase-to-Bit Reduction

Derive the Boolean phase-to-bit Hadamard sandwich and give its complete resource debit. Explain why ordinary phase access does not satisfy its premise.

Solution

Let $s_x=(-1)^{f(x)}$. Starting on a basis state,

$$|x\rangle|y\rangle \xrightarrow{\,I\otimes H\,} \frac{|x\rangle}{\sqrt2} \left(|0\rangle+(-1)^y|1\rangle\right).$$

The declared controlled phase multiplies the $|1\rangle_y$ branch by $s_x$, producing

$$\frac{|x\rangle}{\sqrt2} \left(|0\rangle+(-1)^{y\oplus f(x)}|1\rangle\right).$$

The final Hadamard maps the target to $|y\oplus f(x)\rangle$. Therefore

$$B_f = (I_X\otimes H_y)C_y(P_f)(I_X\otimes H_y).$$

The reduction costs one call to the separately declared exact controlled-phase interface and two Hadamard gates. A plain $P_f$ call is uncontrolled and supplies no reference branch. In particular, the channel cannot distinguish $P_f$ from $-P_f$, although their exact controlled representatives differ, so ordinary phase access does not license this construction.

6. Count Coherent-Lookup Readout

Derive the two marginals of the four-entry lookup state, state what one joint shot returns, and find the mean number of independent shots needed to observe all four rows at least once.

Solution

Write

$$|\Phi_d\rangle = \frac12\sum_{x=0}^{3}|x\rangle|d(x)\rangle.$$

Because the address states and the four distinct value states are orthonormal, tracing out either register removes all off-diagonal terms:

$$\rho_X = \frac14\sum_x|x\rangle\langle x| = \frac{I_4}{4}, \qquad \rho_Y = \frac14\sum_x|d(x)\rangle\langle d(x)| = \frac{I_4}{4}.$$

One joint computational-basis measurement returns exactly one pair $(x,d(x))$, uniformly with probability $1/4$. For independent repetitions, the coupon-collector mean is

$$4H_4 = 4\left(1+\frac12+\frac13+\frac14\right) = \frac{25}{3}.$$

This is a sampling statement, not coherent bulk readout: the unmeasured state encodes correlations, while each shot produces only one classical row.

7. Audit Approximation and Hidden Cost

An algorithm uses $Q=200$ oracle calls. Each costs $5\times10^4$ logical gates, all nonquery work costs $2\times10^6$ logical gates, and each approximate oracle has operator error at most $3\times10^{-6}$. Find the total logical-gate debit and the conservative state-vector error bound. What do they not establish?

Solution

The query contribution is

$$200(5\times10^4)=10^7$$

logical gates. Including nonquery work gives

$$T_{\mathrm{end}} = 10^7+2\times10^6 = 1.2\times10^7$$

logical gates. The telescoping estimate gives

$$\|\widetilde\psi_Q-\psi_Q\| \leq 200(3\times10^{-6}) = 6\times10^{-4}.$$

The first number is meaningful only within the declared logical cost model, and the second is a worst-case deterministic norm bound, not sampling uncertainty or a hardware-noise prediction. Neither proves end-to-end advantage without a classical comparator matched in representation, access, output, accuracy, and success probability, plus an implementation and hardware cost model.

8. Complete a Ten-Field Permutation-Oracle Record

Use the two-qubit four-cycle

$$00\mapsto01\mapsto11\mapsto10\mapsto00, \qquad U_\pi|x\rangle=|\pi(x)\rangle.$$

Complete and interpret the full interface record.

Solution

1. Oracle task and licensed claim — Verify the exact four-cycle action, one declared forward-query output, mathematical period and inverse, and the boundary between an algebraic inverse and a supplied inverse query. No algorithmic speedup or implementation claim is licensed.
2. Instance family, domains, codomains, and promises — Use the single fixed permutation $\pi$ on all four two-bit labels, with no input promise and no hidden family parameter.
3. Registers, dimensions, order, and encodings — Use one two-qubit register $(q_1,q_0)$ in big-endian ascending basis order $00,01,10,11$.
4. Full-space oracle action and phase representative — Use the complete permutation above with every nonzero matrix entry $+1$. The full matrix has columns $|01\rangle,|11\rangle,|00\rangle,|10\rangle$ in the declared input order.
5. Forward, inverse, controlled, powered, and family access — Supply one abstract forward-query interface $U_\pi$ only. Algebraically $U_\pi^4=I$ and $U_\pi^\dagger=U_\pi^3$. An inverse-query primitive is N/A unless separately licensed; three allowed forward calls form the derived word $U_\pi^3$. Controlled, powered-primitive, and family access are N/A because none is supplied.
6. Input state, workspace, garbage, and cleanup — Test $|01\rangle$ with no ancilla, workspace, or garbage. One forward call gives $|11\rangle$; three additional forward calls return the input, but that round trip is not a one-query inverse license.
7. Conversion or reduction, output, measurement, and postprocessing — Computational-basis measurement after one forward call returns $11$ with probability one. No conversion, classical postprocessing, or multi-row output is claimed.
8. Query convention, hidden costs, and fair comparator — Count one abstract forward query for the tested output. Gate decomposition, depth, connectivity, physical time, and inverse-primitive query cost are N/A because this abstract audit does not specify them. A derived inverse uses three forward queries. No classical or quantum advantage comparison is made.
9. Verification data, metric, tolerance, uncertainty, and reproducibility — Verify the four columns, $U_\pi^\dagger U_\pi=I$, $U_\pi^4=I$, $U_\pi^\dagger=U_\pi^3$, and the tested output exactly. A dense binary64 permutation construction has zero maximum-entry residual under absolute tolerance $2\times10^{-14}$; sampling uncertainty is N/A because the calculation is deterministic.
10. Conclusion, stopping point, and canonical handoff — Pass: the complete ideal permutation, period, algebraic inverse, and one-forward-query output are licensed. Stop before circuit synthesis, native gates, query lower bounds, named algorithms, speedup, noise, or hardware.

With columns indexed by inputs $00,01,10,11$, the declared matrix is

$$U_\pi = \begin{pmatrix} 0&0&1&0\\ 1&0&0&0\\ 0&0&0&1\\ 0&1&0&0 \end{pmatrix}.$$

Its columns are an orthonormal permutation of the basis, and direct multiplication confirms all stated period, inverse, and test-vector claims.

References

• M. Araújo, A. Feix, F. Costa, and Č. Brukner, “Quantum circuits cannot control unknown operations,” New Journal of Physics 16, 093026 (2014), doi:10.1088/1367-2630/16/9/093026.
• R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf, “Quantum lower bounds by polynomials,” Journal of the ACM 48(4), 778–797 (2001), doi:10.1145/502090.502097.
• C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, “Strengths and weaknesses of quantum computing,” SIAM Journal on Computing 26(5), 1510–1523 (1997), doi:10.1137/S0097539796300933.
• E. Bernstein and U. Vazirani, “Quantum complexity theory,” SIAM Journal on Computing 26(5), 1411–1473 (1997), doi:10.1137/S0097539796300921.
• A. Berthiaume and G. Brassard, “Oracle quantum computing,” Journal of Modern Optics 41(12), 2521–2535 (1994), doi:10.1080/09500349414552351.
• A. M. Childs and W. van Dam, “Quantum algorithms for algebraic problems,” Reviews of Modern Physics 82, 1–52 (2010), doi:10.1103/RevModPhys.82.1.
• R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, “Quantum algorithms revisited,” Proceedings of the Royal Society A 454, 339–354 (1998), doi:10.1098/rspa.1998.0164.
• D. Deutsch, “Quantum theory, the Church–Turing principle and the universal quantum computer,” Proceedings of the Royal Society A 400, 97–117 (1985), doi:10.1098/rspa.1985.0070.
• D. Deutsch and R. Jozsa, “Rapid solution of problems by quantum computation,” Proceedings of the Royal Society A 439, 553–558 (1992), doi:10.1098/rspa.1992.0167.
• L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 212–219 (1996), doi:10.1145/237814.237866.
• A. Montanaro, “Quantum algorithms: an overview,” npj Quantum Information 2, 15023 (2016), doi:10.1038/npjqi.2015.23.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary ed., Cambridge University Press (2010), doi:10.1017/CBO9780511976667.
• J. Watrous, The Theory of Quantum Information, Cambridge University Press (2018), doi:10.1017/9781316848142.