How many uses of an unknown physical channel are needed before a spectral quantum algorithm can use its matrix coherently?
For unknown unital channels, this repository establishes the optimal dimension order at fixed accuracy. An explicit compiler uses quadratically many ordinary channel calls. A matching lower bound holds already for unknown unitary channels, because coherent Liouville access can expose the unitary's inverse.
Let
The input interface is ordinary forward channel access. The output guarantees are in the unhalved diamond norm, including arbitrary reference-entangled data.
| Requested quantum output | Constructive ordinary-channel cost | Necessary cost |
|---|---|---|
| Evolution |
|
At |
| Complete unitary with exact designated block |
|
At any fixed sufficiently small accuracy, the necessary and sufficient call order is therefore
For
The construction generates coherent controls and inverses of its output operations with the same query order. It does not require controlled or inverse access to the unknown channel, a Stinespring dilation, a Kraus description or QRAM. The resource account charges every Choi-program preparation and separates queries from known gates, finite synthesis and workspace.
A fresh Choi state and a known controlled swap form one mixed program. Its partially transposed first moment contains the desired Liouville matrix. For unital channels, the relevant program marginal is maximally mixed, so the collision second moment is exactly the identity. The inherited program-variance estimate then gives the quadratic construction.
For a unitary channel,
The Liouville construction, Hermitian-preserving map exponentiation, variance estimate, polynomial transformation and inversion theorem are credited in related work. The contribution is the valid unital-case compiler together with the matching fixed-accuracy operational frontier. The original Liouville preprint already advertised the improved exponent before its generic error bound was corrected; that version history is stated explicitly rather than treated as a new numerical scaling alone.
With the additional promise of a known depolarizing probability below one, the same compiler and a known commuting correction also approximate a clean unknown unitary from its noisy channel. The worked channel examples derive that finite-noise upper bound and its calibration and precision limits.
| Question | Authoritative page |
|---|---|
| What is supplied, counted and produced? | Model and normalization |
| Why does the program marginal improve the full-channel bound? | Collision compiler and proof |
| How is an exact designated block obtained with complete-unitary error control? | Block-encoding compiler |
| Why must every ordinary-query compiler pay the dimension cost? | Inversion reduction and lower bound |
| What do known gates, precision, memory and work return cost? | Resources |
| What happens for unitary and noisy-unitary channels? | Examples |
| What is matched and what remains open? | Interpretation |
| Which results and methods are inherited? | Related work and bibliography |
| Which finite identities and channels were checked? | Verification |
The science guide connects the proof dependencies, and llms.txt maps reader intentions to the same authoritative files.
The learning guide starts from a physical channel and follows the mechanism to the dimension frontier. Its single educational anchor is John Watrous, The Theory of Quantum Information (2018). The source bridge translates the book’s conventions and identifies the research ingredients supplied here. The 30-milestone map connects background objects to the complete contribution; it is a common understanding map rather than a record of a reader’s progress.
python3 -m pip install -r verification/requirements.txt
OPENBLAS_NUM_THREADS=1 python3 verification/verify.pyThe checked-in report records complex unital fixtures, nonunital boundaries, complete collision diagnostics, controlled extensions, inverse extraction and the known-noise correction. Choi-distance diagnostics are labeled as finite consistency checks, rather than diamond-norm upper certificates. The general results follow from the analytical proofs.
The channel is promised unital and memoryless; that promise is not learned for free. The lower bound permits arbitrary known controls, memory and causal adaptation under a hard query cap. The output is an actual approximate quantum operation on vectorized data, rather than a classical estimate or a virtual expectation-value reconstruction. Physical implementation uses
The full precision frontier, optimal long-time dependence, optimal synthesis constants, hardware noise thresholds and an application-level classical comparison remain outside the matched theorem. Structured channel families and stronger supplied access can have lower costs.
This repository serves as a record of the work and a guide for the author’s self-directed learning. For discussion or potential collaboration, please contact Ruge Lin at gogoko699@gmail.com.