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.

We will compare bit, value and phase queries, identify information lost by changing the query, and distinguish one query from the gates needed to implement it. The question is what an algorithm can access; algorithm-specific success and lower bounds are developed separately.

Helpful background. Reversible computation explains full-space unitary embeddings and workspace; phase kickback derives conversion of a value into a coherent phase.

Which operation does one query supply?

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 following examples differ even when they encode the same function:

Query	Action	Important distinction
Bitwise XOR	$B_f\lvert x,y\rangle=\lvert x,y\oplus f(x)\rangle$	The same query is its inverse.
Modular addition	$O_f^{(+)}\lvert x,y\rangle=\lvert x,y+f(x)\bmod M\rangle$	The inverse subtracts; target negation can construct it.
Fixed character	$P_{f,k}\lvert x\rangle=\omega_M^{k f(x)}\lvert x\rangle$	Only relative phases are observable without an external reference.
Coherent character family	$D_f\lvert x,k\rangle=\omega_M^{k f(x)}\lvert x,k\rangle$	A quantum label compares characters and permits value recovery.

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.

For replacement on a promised query subspace, the full output vectors must agree:

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

If every query input lies in this subspace, one may replace $U_f$ by $V_f$. Equality of the compressed blocks $P U_fP=P V_fP$, where $P=\Pi_D\otimes I$, is not enough unless both maps also preserve the subspace. Compression discards any amplitude that leaves it. For example, in three dimensions take $P=|0\rangle\langle0|$, let $U$ swap $0$ with $1$, and let $V$ swap $0$ with $2$. Both compressed blocks vanish, but $U|0\rangle=|1\rangle$ and $V|0\rangle=|2\rangle$ are orthogonal.

A coherent amplitude outside the promised input domain can encounter different extensions and later interfere with other branches. A restriction on the hidden function, a restriction on query inputs and a promise of no leakage are therefore different assumptions.

If controlled access will be used, one must also fix the unitary’s phase relative to the reference branch. The uncontrolled channels of $U$ and $e^{i\gamma}U$ coincide, while their controlled representatives can differ observably.

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.$$

For this particular interface, inverse access can be constructed from one forward query and two known target negations. Define $J|y\rangle=|-y\bmod M\rangle$. Then

$$O_f^{(-)}=(I\otimes J)O_f^{(+)}(I\otimes J), \qquad J^2=I.$$

This follows by tracking $y\mapsto-y\mapsto-y+f(x)\mapsto y-f(x)$. It costs one forward query plus the gates for $J$; it is a special consequence of the supplied addition action, not a method for inverting an arbitrary unknown unitary.

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 explains how to embed a many-to-one function using targets and workspace. In a query model those gates may be hidden inside the supplied operation; an implementation must still perform them.

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. The two values $a,b\in\mathbb Z_M$ receive different scalar phases exactly when

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

The map $a\mapsto\omega_M^{ka}$ is injective precisely when $\gcd(k,M)=1$. Otherwise its kernel identifies several values. Even when this scalar map is injective, an uncontrolled phase oracle does not reveal an absolute constant offset: replacing $f(x)$ by $f(x)+c$ multiplies every branch by the same scalar $\omega_M^{kc}$. Only differences between branches are observable without an additional reference. These are two distinct losses of information: a character kernel and an unobservable common phase.

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}.$$

Grover search uses this reflection together with a second reflection to increase marked-state probability.

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. A classical choice of one fixed $k$ does not supply this coherent superposition of characters. Quantum Fourier transform derives the transform circuits and their costs.

Unitary and channel oracles form further interface classes. An ordinary unitary query preserves coherence, but its overall phase is still unobservable unless the access includes a coherent reference. A general channel query may also lose information through an environment. The channel alone does not specify the relative phase needed to control a unitary realization. Sparse-Hamiltonian, block-encoding, state-preparation, QRAM and noisy-channel queries each require a specific definition; 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 construct controlled access from an arbitrary black-box channel. Controlled operations explains the missing phase reference and the additional physical structure that can sometimes supply it.

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 shows how this distinction affects the cost of resolving a phase.

Equivalences Require Declared Capabilities

For Boolean $f$, Phase Kickback derives the clean conversion

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

Preparing the target in $|-\rangle$ therefore realizes one phase query from one bit query, returning the target unchanged.

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 the two forms are equivalent with the additional controlled access above, but not under arbitrary access assumptions. A promise fixing a known reference value of $f$ can also remove the complement ambiguity; that is extra information about the instance family.

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. A supplied clean query includes this cleanup; a known circuit may need to compute, copy its output and reverse its workspace computation.

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.

A classical truth table does not check relative phases or the coherence retained after discarding workspace. Useful comparisons include complete basis action, a superposition input, target return and any leakage from the promised subspace. A controlled-reference test is needed when a representative phase matters.

Query count and implementation cost

An oracle query is one use of the specified operation. To translate a query count into total cost, use one consistent unit, such as logical gate count or execution time, and include

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

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 develops this comparison of inputs, outputs and total costs; query complexity studies the number of calls when the access model is fixed.

Worked example: 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 bit oracles are $B_h|x,y\rangle=|x,y\oplus h(x)\rangle$, with $h=f$ or $g$. Their phase matrices satisfy $P_f=\operatorname{diag}(1,-1,-1,1)$ and $P_g=-P_f$. These uncontrolled phase channels agree on every input, including inputs entangled with a reference. Bit access nevertheless distinguishes the pair.

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.

Worked example: 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.$$

Use register order $x_1,x_0,y_1,y_0$ and prepare $|++\rangle_X|00\rangle_Y$. The complete sixteen-dimensional XOR permutation is an involution, so a second query can undo the first. There is no extra workspace in this specified operation.

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.

This experiment uses two preparation Hadamards and one query; a second query reverses it if no measurement has intervened. Building or loading the table is an additional task. A single superposition query does not return all table entries as classical data.

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 worked example.

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 chosen 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. Convert controlled phase access to bit access

Derive the Boolean phase-to-bit Hadamard sandwich and count its queries and gates. 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 provide 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. Approximation and implementation 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 count 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. Invert a permutation using forward calls

Suppose a forward query implements the two-qubit cycle

$$00\mapsto01\mapsto11\mapsto10\mapsto00.$$

Write its matrix in increasing binary order, find its period and inverse, and distinguish a construction using repeated forward calls from a supplied inverse-query primitive.

Solution

With columns indexed by inputs $00,01,10,11$,

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

Each basis vector travels once around a four-cycle, so $U_\pi^4=I$ and $U_\pi^\dagger=U_\pi^3$. For example, one query takes $|01\rangle$ to $|11\rangle$, and three further queries return it to $|01\rangle$. Thus three forward calls implement an inverse. A separately supplied inverse primitive could count as one inverse query under a different model. The period construction alone does not supply such a primitive or a controlled query.

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.