Alphabeta MathQuantum Algorithms
This category studies quantum algorithms as finite mathematical procedures on explicitly encoded finite-dimensional complex vector spaces. It develops the register, circuit, oracle, probability, and cost interfaces needed to state an algorithm precisely, then proves correctness, termination, success probability, query complexity, gate complexity, and bit complexity as separate results. Early pages cover reversible computation, Fourier sampling, phase estimation, order finding, search, and query lower bounds. Later branches treat quantum walks, Hamiltonian simulation, block encodings, signal processing, singular value transformation, linear systems, sampling, optimization, complexity, communication, and adiabatic computation. The path is deliberately branching: Fourier methods support hidden-subgroup and number-theoretic algorithms, while walk and simulation methods have their own mathematical prerequisites. Each algorithm states its input representation and access model, including the cost of controlled or inverse queries, state preparation, precision, and classical post-processing. A speedup claim is tied to those explicit costs and proved hypotheses. Physical implementations and empirical motivation may be discussed as context, but they do not supply mathematical assumptions or proof steps.
Pathway
Pages are grouped by how many dependency steps into this group they sit. Everything a page needs from this group appears above it.
Level 0
11 pagesThis page defines end-to-end channel and output contracts and proves product-state and tensor-channel error bounds, including final-measurement variation for arbitrary reference inputs.
5 definitions, 3 algorithms, 4 lemmas, 1 proposition, 10 theorems, 1 remarkExamples & counterexamples →- Block Encodings10 results
The page fixes a finite-dimensional convention for representing a matrix as the normalized all-zero compression of a supplied unitary.
2 definitions, 2 algorithms, 1 lemma, 5 theoremsExamples & counterexamples → This page fixes the interfaces used to state promise-query algorithms and compare their resources.
13 definitions, 1 theoremExamples & counterexamples →- Continuous-Time Quantum Walks13 results
A continuous-time quantum walk on a finite register is the matrix evolution U H(t) for a declared self-adjoint generator H.
4 definitions, 2 algorithms, 2 lemmas, 5 theoremsExamples & counterexamples → This page fixes the row-stochastic convention P xy=Pr(y∣ x) and constructs the row-preparation isometry and its self-adjoint discriminant.
6 definitions, 4 lemmas, 4 theoremsExamples & counterexamples →- Finite Abelian Fourier Analysis19 results
This page develops the character dual of a finite abelian group, the normalized negative-character Fourier transform, and its orthogonality, inversion, Parseval, convolution, quotient, annihilator, and coset identities.
4 definitions, 4 lemmas, 11 theoremsExamples & counterexamples → - QMA Verification and Local Hamiltonian29 results
This page defines QMA verifiers over the QC14 full-list uniform circuit model, with an explicit witness register, zero-initialized verifier workspace, and an acceptance effect obtained by compression to the witness.
6 definitions, 1 algorithm, 17 lemmas, 5 theoremsExamples & counterexamples → - Quantum Communication and Fingerprinting21 results
This page develops finite simultaneous-message protocols, their resource declarations, and equality fingerprints.
5 definitions, 1 algorithm, 8 lemmas, 6 theorems, 1 remarkExamples & counterexamples → This page defines promise-class interfaces in the fixed QC14 model: exact finite gates, full-list uniform circuit generation, and unconstrained behavior outside the promise.
4 definitions, 1 algorithm, 3 lemmas, 4 theorems, 1 remarkExamples & counterexamples →- Quantum Fourier-Transform Circuits14 results
This page fixes the positive-sign cyclic QFT as the inverse of the negative-sign, unitary-normalized discrete Fourier transform.
2 definitions, 2 algorithms, 4 lemmas, 6 theoremsExamples & counterexamples → - Quantum Signal Processing21 results
The page fixes the Hermitian-reflection signal matrix, ordered phase product, coefficient-conjugation convention, and controlled scalar convention.
2 definitions, 4 algorithms, 7 lemmas, 8 theoremsExamples & counterexamples →
Level 1
6 pages- Amplitude Amplification19 results
This page defines amplitude amplification for a supplied measurement-free unitary and orthogonal success projection.
1 definition, 5 algorithms, 1 lemma, 1 proposition, 11 theoremsExamples & counterexamples → This page develops the finite abelian hidden-subgroup problem from an explicitly encoded hiding oracle through Fourier sampling and common-kernel recovery.
1 definition, 2 algorithms, 3 lemmas, 3 theorems, 1 remarkExamples & counterexamples →This page treats time-independent Hamiltonians as finite-dimensional self-adjoint matrices and defines simulation error in operator norm.
5 definitions, 2 algorithms, 1 lemma, 4 theorems, 1 remarkExamples & counterexamples →- Quantum Phase Estimation12 results
This page fixes phase modulo one, the big-endian phase-register convention, circular distance, and the separate controlled-power and repeated-controlled-unitary access models.
2 definitions, 1 algorithm, 5 lemmas, 4 theoremsExamples & counterexamples → - Quantum Singular-Value Transformation11 results
The page defines a finite projected-unitary encoding of a rectangular map, proves its singular-plane decomposition, and fixes odd and even singular-value transforms, including their distinct kernel conventions.
2 definitions, 1 algorithm, 3 lemmas, 5 theoremsExamples & counterexamples → This page fixes the standard XOR query and the binary phase query for a total Boolean function.
4 definitions, 1 algorithm, 6 theoremsExamples & counterexamples →
Level 2
9 pagesThis page gives a finite-dimensional account of adiabatic evolution and its circuit relationship.
2 definitions, 2 algorithms, 8 lemmas, 4 theoremsExamples & counterexamples →- Amplitude Estimation and Counting22 results
This page fixes the signed Grover iterate, the amplitude and counting input/output contracts, and separate controlled-power and repeated-controlled-unitary access modes.
1 definition, 6 algorithms, 6 lemmas, 9 theoremsExamples & counterexamples → - Exact Oracle Algorithms14 results
This page fixes the constant-versus-balanced Deutsch promise, the Deutsch–Jozsa promise on n-bit addresses (encoded by an N=2ⁿ-bit truth table), and the no-offset Bernstein–Vazirani promise.
3 definitions, 3 algorithms, 1 lemma, 7 theoremsExamples & counterexamples → This page derives the invariant marked/unmarked plane and the exact success law after an integer number of Grover iterates.
1 definition, 4 algorithms, 4 lemmas, 3 propositions, 9 theoremsExamples & counterexamples →An LCU input is a finite ordered decomposition together with complete PREPARE, SELECT, inverse, controlled-access, and cost contracts.
4 definitions, 3 algorithms, 3 lemmas, 5 theoremsExamples & counterexamples →- Polynomial Method and Approximate Degree14 results
This page develops the polynomial method for an explicitly oracle-only bit-query model.
3 definitions, 6 lemmas, 1 proposition, 4 theoremsExamples & counterexamples → This page defines denominator-bounded rational reconstruction using normalized finite continued fractions and an exact integer window.
1 definition, 3 algorithms, 3 lemmas, 6 theoremsExamples & counterexamples →This page distinguishes the state-dependent spectral law from a phase-estimation output distribution: QPE samples a finite kernel mixture, and its postmeasurement system state is generally a coherent sum across eigenspaces.
2 definitions, 3 algorithms, 1 lemma, 4 theoremsExamples & counterexamples →Finite reversible chains give the stationary mass and marked-state promises used by both classical and quantum search.
5 definitions, 2 algorithms, 4 lemmas, 5 theoremsExamples & counterexamples →
Level 3
8 pagesThis page fixes the finite partial Boolean query model and develops the signed general adversary method with the same XOR oracle and operator-norm convention throughout.
6 definitions, 2 algorithms, 10 lemmas, 2 propositions, 9 theoremsExamples & counterexamples →This page treats finite cyclic discrete logarithm with explicit encodings and costed operation interfaces, the finite abelian hidden-shift promise and its…
2 definitions, 4 algorithms, 5 lemmas, 5 theorems, 1 remarkExamples & counterexamples →This page fixes the standard XOR bit-query model, the empty-versus-singleton promise, and the query-address projectors.
3 definitions, 2 algorithms, 6 lemmas, 5 theoremsExamples & counterexamples →This page fixes a finite probability law, an exactly encoded bounded observable, and the success event for estimating its expectation.
2 definitions, 4 algorithms, 5 lemmas, 5 theoremsExamples & counterexamples →An exact Hermitian block encoding supplies the normalized compression H/α, while the access record separately charges U, U^, controlled calls, projector reflections, state preparation, phase synthesis, and circuit costs.
2 definitions, 3 algorithms, 6 lemmas, 7 theoremsExamples & counterexamples →- Shor’s Factoring Algorithm13 results
This page gives a bounded-error factoring procedure for a promised composite integer N≥4.
1 definition, 2 algorithms, 5 lemmas, 5 theoremsExamples & counterexamples → This page defines the coordinate vector space F 2ⁿ, formalizes Simon’s nonzero hidden-XOR-period promise for total functions with output width at least n-1, and gives an explicit basis for the (n-1)-dimensional annihilator.
4 definitions, 3 algorithms, 2 lemmas, 7 theoremsExamples & counterexamples →This page develops a finite mathematical model of topological computation: fusion inputs and measurements, an initial encoded state or costed preparation procedure, an…
10 definitions, 2 algorithms, 5 lemmas, 7 theoremsExamples & counterexamples →
Level 4
1 pageThis page specifies the state-output QLSP task, a rectangular Hermitian dilation, and the finite sine-window HHL circuit in the signed-eigenvalue convention.
4 definitions, 1 algorithm, 11 lemmas, 4 theoremsExamples & counterexamples →
Level 5
1 pageThis page fixes the block-encoded QLSP promise, its normalization δ=γ/α, and the required state-preparation and controlled/inverse access.
3 definitions, 4 algorithms, 7 lemmas, 5 theoremsExamples & counterexamples →
Level 6
1 pageThis page fixes the finite primal-dual SDP convention, proves the local strong-duality and matrix multiplicative-weights bridges, and gives finite coherent Gibbs/trace…
9 definitions, 5 algorithms, 15 lemmas, 15 theoremsExamples & counterexamples →