QuantumComputinglib learn · inspect · formalize
Checked on this commit 4,524 public declarations commit ab8f277c5704 Build record

Structure before circuit tricks

Envelopes and coherent rejection

Is a reference state closer to the target than the uniform state in a controllable sense?

\[p_{\rm succ}=\frac{\|f\|_2^2}{C^2\|g\|_2^2}=\kappa_{\rm env}^{-2},\qquad C\ge\max_{g_j\ne0}|f_j/g_j|\]

What this technique preserves

Prepare g, apply a controlled contraction f/(Cg) on its support, and retain the success branch. Costs of g, the ratio and amplification must all be paid.

Hypotheses and hidden contracts

  • support(f) subset support(g), with f/g defined as zero off support(g)
  • C>0, nonzero f and g, and a verified pointwise domination bound
  • Magnitude and complex phase of the ratio implemented coherently

Mathematical proof mechanism

This is an authored reusable derivation guide, not a claim that the full family has been source-assimilated.

  1. Write the reference amplitude as g_j/||g||.
  2. Multiply the accepted branch by f_j/(C g_j); the g_j factor cancels on support.
  3. Sum squared accepted amplitudes to obtain success probability, then normalize.

Exact Lean substrates

No local transport theorem is bound to this record. Do not infer formal truth from its position in the atlas.

Do not cross this boundary

Changing from probability sampling to amplitudes requires square roots and phase handling. An envelope with small kappa is not automatically easy to prepare.

Related transports

Sampling envelope meets function structure — proposal

Source and prior-art ledger

Quantum Rejection Sampling

primary-metadata-checked Authors' publication page: quantum state generation, query characterization and matching lower bound

Prior art for coherent amplitude reweighting. Novelty must be in an explicit structured envelope, guarantees, implementation or model-matched bound, not in rejection sampling itself.

Copy mathematical mechanism as LaTeX
% Authored mechanism lesson; not a new theorem certificate.
\section*{Envelopes and coherent rejection}
Is a reference state closer to the target than the uniform state in a controllable sense?
\[
p_{\rm succ}=\frac{\|f\|_2^2}{C^2\|g\|_2^2}=\kappa_{\rm env}^{-2},\qquad C\ge\max_{g_j\ne0}|f_j/g_j|
\]
Prepare g, apply a controlled contraction f/(Cg) on its support, and retain the success branch. Costs of g, the ratio and amplification must all be paid.
\paragraph{Hypotheses and contracts.}
\begin{enumerate}
\item support(f) subset support(g), with f/g defined as zero off support(g)
\item C>0, nonzero f and g, and a verified pointwise domination bound
\item Magnitude and complex phase of the ratio implemented coherently
\end{enumerate}
\paragraph{Mathematical proof mechanism.}
This is a reusable derivation guide; exact certified scope is given by the linked Lean signatures.
\begin{enumerate}
\item Write the reference amplitude as g\_j/||g||.
\item Multiply the accepted branch by f\_j/(C g\_j); the g\_j factor cancels on support.
\item Sum squared accepted amplitudes to obtain success probability, then normalize.
\end{enumerate}
\paragraph{Boundary.} Changing from probability sampling to amplitudes requires square roots and phase handling. An envelope with small kappa is not automatically easy to prepare.

Download LaTeX