Theoretical computer science

A formal language is a set of finite strings over a fixed finite alphabet.

A parallel string-rewriting system: at each generation, every symbol is replaced simultaneously by its assigned word. Symbols can also encode drawing commands such as moving forward or turning. Large recursively defined drawings can be queried without expanding the whole word by precomputing the length, displacement, and rotation of each expanded block.

A binary string is a finite word over the alphabet $\{0,1\}$. There are $2^n$ strings of length $n$. Finite binary strings have an effective bijection with natural numbers, so computable enumerability and immunity apply to sets of strings.

A binary string with $n$ zeroes and $j$ ones is determined by its $j$ one-positions, giving $\left(\genfrac{}{}{0ex}{}{n+j}{j}\right)$ possibilities. Sum for $0\le j\le m$ and apply the hockey-stick identity. Equivalently, distribute at most $m$ ones among the $n+1$ gaps around the zeroes and add a slack count; stars and bars counts $n+2$ nonnegative counts summing to $m$.

A self-delimiting code permits a decoder to identify the end of a code without an external length marker. Encoding a binary word of length $\ell$ by $\ell$ ones, a zero and the word uses $2\ell +1$ bits. This yields an $O(\log n)$ description of a natural number in an incompressibility proof.

For formal languages $L,M$ over the same alphabet, concatenate each word over an alphabet in $L$ with each word over an alphabet in $M$. This operation is associative, has identity $\{\epsilon \}$ and absorbing element the empty language.

The formal language containing no words over an alphabet. It differs from the language containing only the empty word, which is a multiplicative identity for concatenation of formal languages.

A Turing machine is an abstract computational model with a finite control, an unbounded tape and a head that reads, writes and moves on the tape.

A designated tape alphabet symbol occupying unused cells of a Turing machine. It is excluded from the input alphabet, so a finite input word occupies a finite region of an otherwise blank tape.

A finite string describing a Turing machine's states, alphabets, transition rules and designated initial and halting states. Standard encodings have a decidable language of valid descriptions. A syntactic property of an encoding need not be an extensional property of programs; for example, adding an unreachable state changes state count without changing the accepted formal language.

A Turing machine with a fixed finite number of tapes and a head for each tape. One transition reads the scanned symbols, updates them and moves the heads. This model accepts the same computably enumerable languages as a single-tape Turing machine, but step counts can differ.

A Turing machine with one read-write tape. Every multitape Turing machine can be simulated by a single-tape Turing machine, using delimited tape portions and marked head positions. The simulation preserves the accepted formal language and whether a computation halts, while possibly increasing time complexity.

A deterministic single-tape Turing machine that leaves every scanned symbol unchanged and moves one cell right after every nonhalting transition. Such machines decide exactly the regular languages. A deterministic finite automaton simulates the finite control, with accepting states determined by the blank-only continuation after the input; conversely, a machine simulating a deterministic finite automaton halts on the first blank.

An instantaneous description records the current control state, head position, and tape contents. For a tape blank outside a finite window, a word $huqvh$ records the symbols $u$ to the left of the head and $v$ from the scanned cell rightward, with unrecorded cells blank. If $v$ is empty, the head scans an implicit blank. Extra outer blanks can represent the same infinite tape. The instruction of a Turing machine determines its successor description.

For a Turing machine, the one-step binary relation between Turing machine configurations specified by its Turing machine instructions. Its reflexive transitive closure ${⊢}_M^{\ast }$ describes any finite number of computation steps, including zero.

For a deterministic single-tape Turing machine, an instruction reads a state $q$ and scanned tape symbol $a$, writes $b$, changes state to $p$, and moves the head one cell left, one cell right, or not at all according to $D$. The state and tape alphabets are finite; an undefined transition halts. A dedicated terminal state can be introduced by directing undefined transitions to it without changing whether computation halts.

Encode the cells immediately left of the head in a reversed positional stack $L$, and the current and right cells in $R$. Quotient and remainder by the alphabet base read and remove cells; multiplication by that base pushes a cell. The resulting local tape transitions are primitive recursive, which makes them directly implementable on Church numerals.

A modular machine of modulus $m>1$ acts on pairs in ${\mathbb{N}}^2$. Each instruction $(a,b,c,R)$ or $(a,b,c,L)$ has $0\le a,b<m$ and $0\le c<m^2$, and at most one instruction is assigned to each residue pair $(a,b)$. The two transition types are $(mu+a,mv+b)\mapsto (m^{2}u+c,v)$ and $(mu+a,mv+b)\mapsto (u,m^{2}v+c)$. These finite arithmetic operations can encode a Turing machine; a designated terminal configuration can have a nonrecursive halting set.

A modular machine can be encoded by HNN extensions of $K={\mathbb{Z}}^2\ast ⟨t⟩$. The kernel of $K\to {\mathbb{Z}}^2$ has a free basis of a group $t(r,s)=x^{-r}{y}^{-s}t{x}^r{y}^s$. Associated-subgroup maps send these basis elements according to the two arithmetic transition types. In the resulting group, membership of $t(r,s)$ in the subgroup generated by $t$ and the instruction stable letters is equivalent to $(r,s)\in H_0(\mathcal{M})$. One more HNN extension centralizes that finitely generated subgroup, converting membership to equality and hence to the word problem for a group.

For a modular machine whose $(0,0)$ is terminal, $H_0(\mathcal{M})$ is the set of configurations whose forward computation reaches exactly $(0,0)$, including the zero-step computation there. It may differ from the set of configurations stopping at any terminal configuration. Determinism makes membership invariant along each instruction edge.

In a deterministic computation, every configuration and input symbol determine at most one next configuration.

A reversible computation has an injective transition function, so its preceding configuration can be recovered from its current configuration. Any finite classical computation can be simulated reversibly while retaining enough workspace to uncompute its temporary results.

A reversible circuit is composed of bijective gates. The Toffoli gate is universal for reversible Boolean computation when ancillary bits are available.

A nondeterministic computation may have several possible next configurations and accepts when at least one computation path accepts.

An oracle machine may query membership in a fixed language in one computation step.

A function oracle supplies access to an unknown function $f$: given an allowed input $x$, one query returns $f(x)$. Query complexity counts these accesses separately from known local computation. A classical query receives one definite answer; a quantum oracle specifies coherent access through a unitary operator, allowing inputs in quantum superposition. The distinction is part of the access model, not a change to the mathematical function.

A Boolean quantum oracle preserves $x$ and adds a one-bit value $f(x)$ into an answer qubit by exclusive or. On known computational-basis states, its output determines the same value as a classical function oracle query.

A relativized complexity class ${\mathcal{C}}^A$ allows every machine defining $\mathcal{C}$ to query the same oracle $A$.

A Boolean operation is a Boolean function taking truth values encoded as bits: $0$ means false and $1$ means true. These operations supply the concrete two-valued interpretation of a Boolean algebra. A Boolean valuation fixes the inputs; a truth table lists every possible input. With two input bits there are four rows.

The basic logical connectives are logical conjunction (AND, $P\wedge Q$, both true), logical disjunction (OR, $P\vee Q$, at least one true), exclusive or (XOR, $P\oplus Q$, exactly one true), and logical negation (NOT, $\neg P$, the opposite value). OR is inclusive: it accepts the case where both inputs are true.^[ref]

For an original program-condition example, let $P$ mean “the backup is recent” and $Q$ mean “the backup is verified”. A rule requiring a recent, verified backup uses logical conjunction; one accepting either qualification uses logical disjunction. A rule flagging a mismatch between the two qualifications uses exclusive or. A recent, verified backup gives $(P,Q)=(1,1)$: AND and OR accept it, while XOR does not flag it. The last row of the truth table makes this difference explicit.

The same small Boolean operations build larger tests and Boolean circuits. In a programming language, the value of a condition and the procedure for evaluating it both matter. For Boolean operands, Python's and, or, and not implement these logical connectives. Evaluation proceeds from the left; and skips its right operand if the left is false, and or skips it if the left is true. More generally, and and or return an operand, whereas not returns a Boolean.^[ref]

For example, the Python condition denominator != 0 and numerator / denominator > 2 avoids division by zero because the logical conjunction's second test is evaluated only when the first succeeds. Reversing the tests preserves the abstract truth table for defined operands but can raise a division-by-zero error handled through exception handling. A rewrite involving a side effect must also preserve the needed evaluation behavior.

Events turn Boolean operations into operations on sets. For a die with sample space $U=\{1,2,3,4,5,6\}$, let $A=\{2,4,6\}$ be the event “even outcome” and $B=\{4,5,6\}$ the event “outcome at least four”. At outcome $u$, use the indicator functions $P=1_A(u)$ and $Q=1_B(u)$. ThenThus logical conjunction becomes set intersection, logical disjunction becomes set union, exclusive or becomes symmetric difference, and logical negation becomes the complement of a set within $U$. Outcome four satisfies both events, so inclusive logical disjunction includes it and exclusive or excludes it. If the die is fair, these four events have probabilities $1/3$, $2/3$, $1/3$, and $1/2$, respectively. No assumption of independent events is needed for the set identities; indeed $A$ and $B$ here are not independent, since $1/3\ne (1/2)(1/2)$.

Exclusive or returns one exactly when its two input bits differ. Its truth table gives $0\oplus 0=0$, $0\oplus 1=1$, $1\oplus 0=1$, and $1\oplus 1=0$. The identitiesexpress exclusive or using logical conjunction, logical disjunction, and logical negation. The first expression accepts at least one input and then excludes both; the second explicitly lists the two accepted input pairs.

For numerical bits, exclusive or is addition in modular arithmetic modulo two:The binary operation is commutative and associative, because addition modulo two has those properties. It satisfies $x\oplus 0=x$, $x\oplus 1=\neg x$, and $x\oplus x=0$. These identities explain why a bit can be toggled and restored with the same operation.

On binary strings of equal length, bitwise exclusive or applies the one-bit rule separately at each position. For example,A bit mask of $0110$ toggles exactly the middle two bits. Applying the mask twice restores the original binary string: each selected bit changes twice, and each unselected bit stays fixed. This positional operation is distinct from taking the exclusive or of the overall truth values of two integers.

For bits $x_1,\dots ,x_n$, repeated exclusive or computes the parity of the number of ones:An induction proves this: the first bit gives its own parity, and appending a zero preserves it while appending a one changes it. The binary string $10110$ has three ones, so its parity bit is one. Append that parity bit to obtain $101101$, whose six bits have even parity. Flipping the second bit produces $111101$ and changes the combined exclusive or to one, detecting an error. Flipping the third bit as well produces $110101$, with four ones and combined exclusive or zero: an even number of flips can escape this check.

For three inputs, repeated exclusive or means an odd number of true inputs, rather than exactly one: $1\oplus 1\oplus 1=1$. The “exactly one” description applies to the two-input exclusive or. This distinction matters when translating a requirement that exactly one option be selected into a program condition.

Logical negation exchanges zero and one: $\neg 0=1$ and $\neg 1=0$. For a numerical bit $x$, this is $1-x$; applying logical negation twice restores $x$. It acts on the entire propositional formula in its scope. Parentheses therefore matter: $\neg (P\vee Q)$ says that neither condition holds, while $(\neg P)\vee Q$ also accepts every case where $Q$ holds. At $(P,Q)=(1,1)$ their values are zero and one.

On a set, logical negation becomes taking a complement in a fixed universal set. In Boolean operations on events, “not even” selects $\{1,3,5\}$. “Not both even and at least four” selects $\{1,2,3,5\}$; it does not require both qualifications to fail. De Morgan's laws make the scope of these compound negations precise.

A one-input logic gate that complements a bit.

De Morgan's laws exchange logical conjunction and logical disjunction when a logical negation moves across them:Here $\equiv$ denotes logical equivalence: the two propositional formulas agree under every Boolean valuation.^[ref]

A complete verification uses the four rows of a truth table. In input order $(0,0),(0,1),(1,0),(1,1)$, both sides of the first logical equivalence have output sequence $(1,1,1,0)$; both sides of the second have $(1,0,0,0)$. A proof in words is equally short: failure of “both” means at least one failure, whereas failure of “at least one” means both fail. The differing middle rows explain why simply pushing logical negation inward without changing AND to OR is wrong.

For the events in Boolean operations on events, the corresponding set identities areOne can prove these identities by checking an arbitrary set element $u\in U$: its two membership truth values obey De Morgan's laws. The same reasoning works for any two subsets of a common universal set.

For a nested program test, let $R$ mean “backup recent”, $V$ mean “backup verified”, and $O$ mean “manual override authorized”. Rejecting when neither an acceptable backup nor an override is present givesThe transformed condition reads “backup stale or unverified, and no override”. Apply the second of De Morgan's laws at the outside, then the first at the inner logical conjunction. For $(R,V,O)=(1,0,0)$ it rejects; changing only $O$ to one makes it accept. With Boolean operands in Python, not ((recent and verified) or override) and ((not recent) or (not verified)) and (not override) have the same result and inspect the operands in the same order, with the same skipped operands.

For a Boolean function $f$ of $n$ input bits, define its De Morgan dual by complementing every input, applying $f$, and complementing the output:

De Morgan's laws say that the De Morgan dual of logical conjunction is logical disjunction, and conversely. The constant zero Boolean function becomes constant one. This is different from merely negating the output: for AND, output logical negation gives one at $(0,0)$, whereas the De Morgan dual gives zero there.

Taking the De Morgan dual twice restores the original Boolean function:Here each input is complemented twice as well. For a Boolean formula built from AND, OR, NOT and constants, its De Morgan dual can therefore be obtained by exchanging AND with OR and zero with one throughout, leaving input names and NOT in place. A structural induction proves the rule: it holds for an input and each constant, De Morgan's laws handle the two binary logical connectives, and double logical negation handles NOT. This symmetry lets one translate a complex test systematically instead of guessing where its failures occur.

Computational complexity theory classifies computational problems by the resources needed to solve them.

The number of elementary operations on bits required by an algorithm. Arithmetic-operation counts treat operations on entire integers as units, whereas bit complexity charges for the sizes of their operands. An algorithm using few multiplications can therefore require substantially more bit operations when the operands grow. State the model when comparing bounds for repeated squaring or dynamic programming counts.

Parameterized complexity studies an algorithm's resource use as a function of both the encoded input length $N$ and a distinguished nonnegative integer parameter $k$. A small solution size, a dimension or a structural property of a graph can serve as the parameter. Fixed-parameter tractability allows arbitrary computable dependence on $k$ while keeping the exponent of $N$ independent of $k$.

A kernelization is a polynomial-time algorithm mapping a parameterized decision problem instance $(I,k)$ to an equivalent instance $(I^{\prime },k^{\prime })$ of the same problem, with both encoded length $|I^{\prime }|$ and parameter $k^{\prime }$ bounded by a computable function of $k$. Equivalent means that both instances have the same yes/no answer. The bound need not be a polynomial in $k$; a polynomial kernel is the stronger requirement that it is. For a decidable problem, exhaustively solving the bounded output leaves only a computable dependence on $k$, so kernelization yields fixed-parameter tractability.

A parameterized decision problem is fixed-parameter tractable if an algorithm decides every instance of encoded length $N$ and parameter $k$ in running time at most $f(k)N^c$, for a computable function $f$ and a constant $c$ independent of $k$. The distinction is in the exponent: $2^k{N}^3$ has this form, whereas an $N^k$ bound alone does not establish fixed-parameter tractability. Branching on an uncovered edge gives a fixed-parameter tractable vertex cover decision problem.

Decide whether all input elements are distinct. In the comparison model, this needs $\Omega (n\log n)$ comparisons in the worst case. An accepting decision-tree leaf for distinct keys must force a total order: incomparable keys could otherwise be made equal consistently with its strict comparison outcomes. Thus the $n!$ possible orders require different accepting leaves, giving a decision-tree depth of at least ${\log }_3(n!)=\Omega (n\log n)$ even for three-way comparisons.

A model in which an algorithm learns the relative order or equality of input keys by comparisons. Lower-bound reductions must preserve the information available to each comparison; transforming numbers and allowing stronger tests without justification can change the model. For intervals $(2z_i,2z_i+1)$ built from integers, every endpoint comparison can be simulated by comparing original keys and then fixed offsets.

A single comparison returning one of three outcomes: less than, equal to, or greater than. A comparison model may count this as one operation even when a programming language expresses the outcomes using multiple Boolean tests. Binary search on ordered keys uses one such comparison per inspected position.

Given two weighted formula utility representations with binary rational numbers as weights, decide whether their values agree on every Boolean valuation. This problem is co-NP-complete.

For membership, a valuation witnessing unequal values certifies non-equivalence. Evaluate all propositional formulas and add their weights exactly in polynomial time. For hardness, compare the one-rule base $\{(\theta ,1)\}$ with the empty base. They are equivalent exactly when $\theta$ is an unsatisfiable Boolean formula. Thus even very small weighted rule bases express a universal equivalence question.

The class of decision problems whose complements belong to NP. Equivalently, negative instances admit polynomially bounded witnesses verifiable in polynomial time. A problem is co-NP-complete when it is in co-NP and every problem in co-NP has a polynomial-time reduction to it. Unsatisfiability of a propositional formula is a basic example: its complement is the NP-complete Boolean satisfiability problem.

The number of accesses to an unknown input needed to solve a specified task. The input might be a string with individually readable entries, or an implicitly supplied function. A complete statement specifies deterministic, randomized, or quantum access, the accepted error, and worst-case or expected cost. Quantum query complexity permits coherent input access through a quantum oracle.

Suppose an unknown function on $\{1,\dots ,d{\}}^n$ has exactly one essential variable. Query the diagonal inputs $(t,\dots ,t)$ to find two coordinates values $a,b$ giving distinct outputs; at most $d$ function-evaluation oracle calls suffice because the unary dependence is nonconstant. A query taking value $b$ on an index subset $H$ and $a$ outside it then tests whether the essential coordinate lies in $H$. Repeated halving locates it in at most $\lceil {\log }_{2}n\rceil$ further queries. If $n=1$, no query is needed.

For a matching lower bound with fixed $d$, restrict to $f^{(i)}(x)=1$ when $x_i=1$ and $2$ otherwise. Every query has only two possible replies. A binary decision tree distinguishing the $n$ possible essential indices needs at least $n$ leaves and depth $\lceil {\log }_{2}n\rceil$. Integer outputs in the unrestricted problem need not be binary; the restricted family is what makes this query complexity argument valid.

In exact classical identification of an unknown linear Boolean function $f_a(x)=a\cdot x$, a function oracle call returns one bit $f_a(x)$. The query complexity is exactly $n$ for $n\ge 1$. Queries on the standard basis inputs $e_j$ reveal $a_j$, proving sufficiency. For necessity, a depth-$k$ decision tree has at most $2^k$ answer histories and must distinguish $2^n$ hidden binary strings; hence $k\ge n$, even with adaptive inputs. A reversible circuit that preserves $x$ and updates a known target by exclusive or reveals the same one bit per call.

There is also a useful linear algebra proof. Along a fixed history, the chosen inputs form the rows of a matrix $M$ over the two-element finite field, and the replies specify $Ma$. If there are $k<n$ queries, the rank-nullity theorem gives a nonzero vector $v$ with $Mv=0$. Then $a$ and $a+v$ give identical replies throughout this history. This also explains why adaptive choices cannot evade the bound: equal earlier replies force the same later choices.

Communication complexity studies how much information distributed parties must exchange to compute a function of their separately held inputs. Local computation is free; the resource being counted is communicated bits or qubits, with the allowed shared randomness, quantum entanglement or other correlations specified separately. For a Boolean function $f(x,y)$, a one-way exact protocol has the receiver output $f$ correctly for every input after a single message. One-bit computation using Popescu–Rohrlich boxes shows that this resource measure changes drastically if ideal superquantum boxes are available.

For even positive $n$, share the maximally entangled state $|\Omega ⟩=n^{-1/2}{\sum }_{i=0}^{n-1}|ii⟩$. Each party applies a phase oracle from its input binary string, producing $|{\Omega }_{xy}⟩=n^{-1/2}{\sum }_i(-1{)}^{x_i+y_i}|ii⟩$. Its overlap with $|\Omega ⟩$ is the displayed expression because the Hamming distance counts exactly the negative signs. Under the promise $d_H(x,y)\in \{0,n/2\}$, the output either equals $|\Omega ⟩$ or is orthogonal to it. Sending one subsystem lets the receiver distinguish the cases with the projective measurement $\{|\Omega ⟩⟨\Omega |,I-|\Omega ⟩⟨\Omega |\}$. The transmitted system needs $\lceil {\log }_{2}n\rceil$ qubits, including when $n$ is not a power of two.

A promise problem consists of disjoint sets of YES and NO instances. An algorithm or verifier must obey its correctness guarantees only on their union. Energy problems with separated thresholds are naturally promise problems because intermediate-energy instances require no prescribed answer.

Quantum complexity theory studies resources needed by quantum circuits and quantum algorithms, including time, workspace, and quantum query complexity. Its models specify which input oracles and gate implementations are available; counting oracle calls is different from counting all elementary gates.

BQP is the class of promise problems decided by uniform polynomial-size quantum circuits with bounded error. Completeness $2/3$ and soundness $1/3$ are conventional; BQP error reduction shows that other fixed separated thresholds give the same class.

Independent runs of a BQP algorithm with fresh ancilla qubits can be combined by a classical threshold rule. If completeness exceeds soundness by $\gamma$, a Hoeffding inequality bounds the error after $r$ runs by $e^{-r{\gamma }^2/2}$. Polynomial repetition handles inverse-polynomial gaps. This does not automatically preserve the restricted gate and measurement rules of a stoquastic circuit.

A quantum witness is a polynomial-size quantum state supplied to a verifier as evidence for a YES instance. The verifier fixes its own ancilla qubits independently. Pure quantum witnesses suffice when maximizing a linear acceptance functional on density operators. Quantum witnesses are not generally restricted to basis vectors or product states.

StoqMA is a restricted quantum-verifier class using stoquastic circuits and polynomial-size quantum witnesses. A YES instance has a quantum witness accepted with probability at least $a$; on a NO instance every quantum witness has acceptance at most $b$, with an inverse-polynomial gap $a-b$. An optimal quantum witness can be chosen with nonnegative amplitudes, since the witness acceptance operator is entrywise nonnegative. The quantum witness is generally a superposition, rather than a computational basis vector. The stoquastic acceptance floor explains the lower limit $b\ge 1/2$ for a nontrivial soundness promise.

QMA is the class of promise problems with a polynomial-size quantum witness checked by a uniform polynomial-size quantum circuit. YES instances have an accepting witness with probability at least $2/3$; NO instances have acceptance at most $1/3$ for every witness, including mixed states. The verifier's acceptance is linear in the witness density operator. Inverse-polynomial or exponentially small error can be obtained through QMA error reduction.

For quantum witness embedding $J$, verifier unitary $U$ and accepting projector $\Pi$, the witness acceptance operator is the positive contraction $F=J^{†}{U}^{†}\Pi UJ$. The maximum acceptance over normalized quantum witnesses is ${\lambda }_{\max }(F)$ by the Rayleigh quotient. Restricting to basis quantum witnesses only tests its diagonal entries and need not find that maximum.

For a positive witness acceptance operator on dimension $D$, large trace powers approximate its largest eigenvalue. With an $m$-qubit QMA quantum witness and $d=2m+2$, the usual NO instances give $\mathrm{Tr}(F^d)<2^{-d}$ and YES instances give a value above $2^{-d}$. A closed product-index expansion computes the trace by recomputation with polynomial storage, avoiding logarithms and roots in a real-arithmetic implementation.

Starting from completeness $2/3$ and soundness $1/3$, run an odd number $r$ of parallel copies and take majority. The QMA parallel repetition with entangled witnesses argument proves soundness for arbitrary repeated witnesses. Exponential Markov's inequality gives majority error at most $(2\sqrt{2}/3{)}^r$. Hence $O(\log (1/ϵ))$ copies suffice for error $ϵ$, with polynomial overhead when the target error is inverse-polynomial or exponentially small in input length.

Independent verifier circuits on $r$ witness registers induce a threshold acceptance effect built from tensor products of $M$ and $I-M$, where $M$ is the quantum verifier acceptance operator. In a product eigenbasis of $M$, the effect's eigenvalues are threshold probabilities for independent Bernoulli random variables with parameters given by the selected eigenvalues of $M$. Bounding every parameter on a NO instance bounds the effect's operator norm, even if the actual submitted witness is entangled. Independence is used only for the spectral calculation, not assumed for the witness.

A verifier with clean ancillas and a designated output measurement induces an effect $0\le M\le I$ on the witness register. Its acceptance probability is $\mathrm{Tr}(M\rho )$, and the largest possible acceptance is $\Vert M\Vert$. Spectral bounds on $M$ make the soundness quantifier over all witnesses, including entangled repeated witnesses, explicit.

The quantum query complexity of a task counts uses of an input oracle by a quantum circuit, for a specified success probability. Known gates and workspace operations are not counted as oracle queries, although they contribute to the circuit's full runtime. An efficient query bound therefore need not, by itself, be an efficient gate bound.

A quantum oracle supplies coherent access to a function through a specified unitary operator. For a function with binary string output, the standard construction retains the input and adds the output into an answer quantum register by bitwise exclusive or. This operation is its own inverse, even when the function is not injective. A Boolean quantum oracle is the single-output-bit case; Simon's algorithm uses several answer qubits. Other encodings, such as a modular-addition quantum oracle or a phase gate encoding, require their own explicit query conventions.

A phase oracle encodes a Boolean function in the signs of computational basis states. Its diagonal entries have modulus one, so it is a unitary operator. The usual convention $O_f$ changes the sign when $f(x)=1$. A complemented convention $U_f|x⟩=(-1{)}^{f(x)\oplus 1}|x⟩$ instead changes the sign when $f(x)=0$, with $U_f=-O_f$; $\oplus$ denotes exclusive or. The two conventions differ by a global phase when used without coherent control, but the global phase of a controlled quantum gate makes that difference observable when the quantum oracle is controlled.

An unrestricted Boolean function on $M>2$ inputs cannot be classified as constant or nonconstant with certainty using a single phase oracle query, even with quantum ancillas. Write a purified query input as $|\Psi ⟩={\sum }_x|x⟩|a_x⟩$ with $p_x=\Vert a_x{\Vert }^2$ and ${\sum }_x{p}_x=1$. The zero constant function leaves it unchanged; the function supported only at $j$ produces a vector with inner product $1-2p_j$ with it. Perfect discrimination of pure states requires orthogonality, forcing $p_j=1/2$ for all $j$ and thus $M=2$, a contradiction. This is an exact quantum query complexity obstruction for all nonconstant inputs, rather than the restricted promise used by the Deutsch-Jozsa algorithm.

After $T$ input-bit queries, every probability amplitude is a polynomial of degree at most $T$, because the bit-query matrix entries are affine in the input bits. An acceptance probability is a sum of squared absolute amplitudes and has polynomial degree at most $2T$. Multilinear reduction on the Boolean cube does not increase degree. Exact acceptance therefore implies $Q_E(f)\ge \lceil \mathrm{deg}(f)/2\rceil$. For bounded error the acceptance polynomial only approximates the Boolean function; its exact representing degree is not the relevant bound.

The least worst-case number of input-oracle calls made by a quantum circuit that computes a Boolean function with zero error on every input. Known unitary gates and classical processing do not count toward this quantity; their runtime is a separate cost.

One exact parity query determines whether the first two bits agree. If they agree, a second query reads one of them; otherwise it reads the third bit. Those values respectively determine the three-bit majority function. The matching lower bound follows from its degree-three multilinear polynomial.

Given a function $f$ with an $m$-bit output, accessed through the unitary operator $U_f|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$, quantum collision finding asks for distinct inputs with equal outputs. Here $\oplus$ is bitwise exclusive or on the $m$-bit answer quantum register. The distinctness requirement excludes the uninformative pair $(x,x)$. For a two-to-one function on $N$ inputs, Grover search algorithm methods yield a cube-root quantum query complexity, despite a square-root cost for finding a partner of just one preselected input.

Query a known set of $m$ inputs and store its output table. If no function collision occurs there, each of its $m$ distinct outputs has exactly one partner in the complement, for a two-to-one function. A compute-phase-uncompute construction marks those partners using two function queries and reversible table comparison. Known-subset Grover search then uses $O(\sqrt{(N-m)/m})$ such phase queries. Including table preparation and a final verification query givesChoosing $m\asymp N^{1/3}$ balances both terms and gives $T(m)=O(N^{1/3})$. The Grover rotation angle rounding bound gives success tending to one. This is a query bound; it does not make reversible table lookup free in a gate or physical-memory cost model.

The decision tree model computes a function by adaptively querying input coordinates.

A decision tree represents a deterministic computation of a known Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ by inspecting input bits. Each internal vertex of its binary tree names a coordinate $i$ to query, its two outgoing edges carry answers 0 and 1, and each leaf carries the output 0 or 1. Starting at the root of a tree, read the named bit, follow its answer edge, and repeat until a leaf is reached. Correctness requires the leaf's label to equal $f(x)$ for every input $x$.^[ref]

The next coordinate, or the decision to stop, can depend on earlier answers: this is adaptive querying. The same input always follows the same graph path; adaptivity does not require randomness. A correct leaf must have the same output for every completion of the observed bits. Thus a decision tree can stop as soon as the observations form a query certificate. Querying an already known coordinate adds no information, so we use decision trees without repeated coordinates on a graph path; an efficient tree also removes queries made after the output is already forced.

The motivation is exact computation with shortcuts. If inspecting an input entry is expensive, the question is how much of the input must actually be read. The decision-tree query cost counts these inspections, while local calculations on known values are free in this model; this cost need not equal an implementation's time complexity. Here the Boolean function is specified in advance and must be computed exactly on every input. Decision tree learning instead fits a predictor from data, with a different objective.

Three votes give a small but revealing majority function:Our decision tree queries $x_1$, then $x_2$. If these bits agree, return their common value: two equal votes already force the majority function. If they disagree, query $x_3$ and return its value. The first two queries have a fixed order, but whether a third query occurs is adaptive.

Each internal label in the diagram names the next bit to inspect. Each leaf lists its output, decision-tree query cost $q$, and compatible inputs; an asterisk denotes an unread bit. The two shallow leaves each cover two inputs, while each deeper leaf covers one. Reading every bit would also compute the majority function, but would miss these exact shortcuts.

All eight inputs give the following exhaustive check. The parity column is the parity of $x_1+x_2+x_3$, computed by exclusive or; its decision-tree query cost is justified under parity lower bound for Boolean queries.

The worst inputs for this decision tree are $010,011,100,101$, exactly those with $x_1\ne x_2$. Its actual depth is three. Every exact decision tree for this majority function has depth at least three: after the first query, an adversary can answer the second distinct query with the opposite bit, leaving the last bit decisive. Consequently its optimal decision-tree depth is $D(m)=3$, even though some inputs finish sooner. Every input has a two-bit query certificate, namely two agreeing votes; locating those votes can require a third query. This separates having a short query certificate from finding one.

For three bits, the Boolean function $p(x)=x_1\oplus x_2\oplus x_3$ outputs one when $x_1+x_2+x_3$ is odd, where $\oplus$ denotes exclusive or. Unlike the three-bit majority decision tree, an exact decision tree computing parity must inspect all three bits on every input. If any coordinate is unread, two completions differing only at that coordinate follow the same observed graph path but have opposite parity. A single leaf cannot correctly label both.