Foundations

BQP consists of decision problems with uniform polynomial-size quantum circuits and bounded error, using a specified finite gate model and classical input/output.

QMA gives a polynomial-time quantum verifier a polynomial-qubit witness, accepting some witness on yes-instances and rejecting every witness on no-instances with a bounded completeness/soundness gap.

Bostanci, Huang and Vaikuntanathan's 2026 manuscript constructs a classical oracle O with QMA^O not contained in QCMA^O and BQP^O/qpoly not contained in BQP^O/poly, using a code-intersection problem with strong list-recovery properties.

As reviewed on 10 October 2026, the 2026 classical-oracle separation distinguishes quantum and classical witnesses within a relativized model but leaves the ordinary QMA versus QCMA relation unresolved by that result.

For a two-sender discrete memoryless MAC with independent messages, the capacity region is the closure of rates bounded by I(X1;Y|X2,Q), I(X2;Y|X1,Q) and I(X1,X2;Y|Q), over laws p(q)p(x1|q)p(x2|q)p(y|x1,x2).

For a physically degraded memoryless broadcast channel X→Y1→Y2, independent private-message rates are achieved by superposition with R2≤I(U;Y2) and R1≤I(X;Y1|U), unioned over p(u,x).

For a discrete memoryless relay law p(y2,y3|x1,x2), decode-forward achieves the maximum over p(x1,x2) of min{I(X1,X2;Y3),I(X1;Y2|X2)}.

Decode-forward asks a relay to recover a message or layer before forwarding cooperative codewords; a weak source-to-relay link can bottleneck it.

With iid correlated (X,Y), an encoder observing X and a decoder observing Y have rate-distortion function min[I(X;U)−I(Y;U)] over U−X−Y and reconstruction x-hat(U,Y) meeting the distortion bound.

Two-user interference channels require two messages decoded at their respective receivers under a joint law p(y1,y2|x1,x2).

An interactive proof lets a polynomial-time randomized verifier exchange messages with a computationally unbounded prover.

The equality IP=PSPACE refers to polynomial-time randomized verification with polynomially many interactions and an unrestricted prover.

Zero knowledge requires an efficient simulator for the verifier's allowed view without the witness, with exact, statistical or computational indistinguishability as specified.

The PCP theorem expresses NP=PCP(O(log n),O(1)): a polynomial-time verifier uses logarithmically many random bits and queries a constant number of positions in a polynomial-length proof, with completeness one and bounded soundness such as one-half.

A proof assistant checks that a term establishes a formal proposition under declared axioms and kernel rules.

NIST's project page, updated 5 August 2026 and checked 10 October, lists FIPS 203 ML-KEM, FIPS 204 ML-DSA and FIPS 205 SLH-DSA as final standards published 13 August 2024.

FIPS 203 ML-KEM uses module-LWE-based public-key structure and a key-encapsulation transformation targeting IND-CCA2 security.

FIPS 204 ML-DSA standardizes the Dilithium-derived module-lattice signature design, with ML-DSA-44/65/87 at security categories 2/3/5.

SLH-DSA is a stateless hash-based signature design, while ML-DSA uses module-lattice structure.

A migration inventory must identify long-lived confidential data, key establishment versus signatures, protocol/certificate formats and parameter/revision dependencies.

For a binary symmetric channel with crossover probability 0<p<1/2 and fixed target block error 0<epsilon<1, the best rate has normal approximation C−sqrt(V/n) Q-inverse(epsilon)+O(log(n)/n).

For independent repetitions of a finite-alphabet joint law p(x,y), an encoder observing X and a decoder possessing Y can recover X with vanishing block error at rates above H(X|Y); rates below it are impossible.

For an iid source with law p(x) and specified distortion d(x,x-hat), R(D) minimizes mutual information over reconstruction laws meeting expected distortion D.

Arıkan's transform recursively turns a binary-input memoryless channel into synthetic channels with polarized reliabilities.

For a stationary finite-alphabet process the block entropy per symbol tends to an entropy rate, while correlations can make it smaller than single-symbol entropy.

In an indistinguishability experiment, an efficient adversary selects equal-length messages and receives an encryption of one chosen by a hidden random bit.

Adaptive chosen-ciphertext security allows decryption queries before and after a challenge, excluding the challenge ciphertext itself under the experiment's rules.

Existential unforgeability under chosen-message attack requires that an efficient adversary with a tagging oracle cannot produce a valid tag for a new message with more than negligible probability.

EUF-CMA signature security gives an adversary a public verification key and signing oracle, then tests whether it can produce a valid signature on a previously unsigned message.

A reduction turns a successful scheme attacker into an attacker on a stated assumption, with explicitly related time, query count and success probability.