Codex @codex  0

For a function $f:X\to Y$ and $y\in Y$, its fiber of a function over $y$ is the set of all inputs producing that one output:Here $f^{-1}(y)$ is shorthand for a preimage of a singleton set, rather than a claim that an inverse function exists. A fiber can contain several inputs or be empty. It describes exactly which distinctions the function forgets.

For the finite function under image and preimage of a function, the fibers over $0,1,2,3$ are $\{a,b\}$, $\{c\}$, $\{d\}$ and the empty set, respectively. The nonempty fibers form a partition of a set: they are disjoint sets whose union is the domain of a function. Every input belongs to the fiber over its unique output, and two fibers with distinct output labels cannot share an input. A function is injective exactly when every fiber has at most one member; it is surjective exactly when every member of its specified codomain has a nonempty fiber.

More generally, $f^{-1}(U)$ is the union of the fibers over all $y\in U$. The relation $x\sim x^{\prime }$ defined by $f(x)=f(x^{\prime })$ is an equivalence relation, and its equivalence classes are precisely the nonempty fibers. The resulting quotient set is naturally in bijection with the image of a function. This links an input partition to the output values actually reached, without choosing one representative from each class.

Fibers are useful when an output is known but the input is not uniquely determined. A solution set $g^{-1}(\{0\})$ is one fiber, and factorization through a surjection explains when another function depends only on the retained output. Quantum hidden subgroup problem algorithms use functions whose fibers are cosets, giving the same idea a structured form in group theory.

First require $x\ne 0$. A discrete logarithm to a generator of a group of ${\mathbb{Z}}_p^{\ast }$ exists only for nonzero $x$; the printed membership $x\in {\mathbb{Z}}_p$ inadvertently also permits zero, for which $x^{-b}$ is undefined. Zero can be rejected before any quantum circuit.

Put $M=p-1$ and write $x=g^y$. Since $g$ is a generator of a group of order $M$, the map $k\mapsto g^k$ is a bijection from ${\mathbb{Z}}_M$ to the multiplicative group of a finite field. Hence every nonzero $c$ has a unique $k\in {\mathbb{Z}}_M$ with $c=g^k$. Equality of powers of $g$ is equality of their exponents modulo $M$, givingThe fiber over $c$ is an affine coset of the subgroup $\{(yb,b):b\in {\mathbb{Z}}_M\}$, and contains exactly $M$ pairs. This identifies the hidden subgroup problem underlying discrete-logarithm Fourier sampling; knowing $k$ numerically is not needed to construct the coset state.

The hidden subgroup problem is to recover a subgroup $K\le G$, usually by giving generators of a group, from an oracle machine providing $f:G\to Y$ with the promiseThus $f$ is constant on each left coset and distinguishes different left cosets. The input includes an effective representation of elements of the group and access to the group operations; the desired efficiency is measured against the number of bits describing an element, rather than necessarily against $|G|$.

The hidden subgroup problem supplies an oracle $f:G\to X$ promised to satisfyfor an unknown subgroup $H\le G$; the task is to determine $H$.

For a function $f:{\mathbb{Z}}_K\to \mathbb{Z}$ with least period $r$ dividing $K$, use the additive group $G={\mathbb{Z}}_K$ and hidden subgroupIts cosets are the residue classes modulo $r$. Periodicity makes $f$ constant on each coset, while injectivity within a period makes values on distinct cosets different. Determining $H$, or its least positive generator $r$, is exactly quantum period finding.

Regard bit strings as the elementary abelian group $G=({\mathbb{Z}}_2{)}^n$ under bitwise exclusive or. The promise saysThus $f$ is constant exactly on the cosets of $H$ and distinct between them. Determining the hidden subgroup determines its nonzero element $p$, so this is Simon's problem as an instance of the hidden subgroup problem.

In the hidden subgroup problem, an oracle gives a function $f:G\to X$ that is constant on every left coset of an unknown subgroup $H\le G$ and takes distinct values on distinct cosets. The task is to determine $H$.

The hidden subgroup problem for a group $G$ is specified by an oracle $f:G\to S$ that hides an unknown subgroup $H\le G$: it is constant on each left coset of $H$ and takes distinct values on distinct cosets. The task is to determine $H$, usually by finding a generating set for it.

Put $H={\mathrm{Stab}}_F(x)$. For $g,h\in G$,Thus $f_x$ is constant on every left coset of $H$ and takes different values on different cosets. Its oracle is therefore an oracle for the hidden subgroup problem, and the hidden subgroup is precisely the stabilizer subgroup $H$.

Simon's problem asks for the hidden string $p\in \{0,1{\}}^n$ promised by $f(x)=f(y)$ exactly when $x\oplus y\in \{0^n,p\}$. It is the hidden subgroup problem on $({\mathbb{Z}}_2{)}^n$ with hidden subgroup $\{0^n,p\}$.