arXiv:2611.02441
Barycentric programming: Classical realization of programs for universal quantum processors
Yutaka Hashimoto, Satoshi Yoshida, Mio Murao
Abstract
A programmable quantum processor implements a target unitary using information stored in a classical or quantum program register. For arbitrary unitaries in $\mathrm{SU}(d)$, quantum programs attain the optimal leading-order memory cost, whereas deterministic classical rounding requires twice as much memory for the same diamond-distance error. We show that this gap disappears when classical randomization is allowed. We introduce barycentric programming, which stores the label of a unitary randomly selected from a finite set, with probabilities chosen so that first-order approximation errors cancel in the averaged unitary channel. Consequently, the diamond-distance error scales quadratically with the discretization spacing. For any $ν$-parameter family of unitaries forming a compact, smooth manifold without boundary, this method achieves error $\varepsilon$ using only $(ν/2)\log_2(1/\varepsilon)+O(1)$ classical bits. We also prove a matching lower bound for arbitrary quantum programs, determining the optimal leading-order program size for general unitary families. Thus, classical randomization achieves the optimal scaling $(ν/2+o(1))\log_2(1/\varepsilon)$ without requiring coherent quantum memory.
AI Summary
A programmable quantum processor approximates a target unitary using a finite program register. This paper asks whether finite classical memory, with randomized encoding, can match the optimal leading-order quantum program cost, rather than the factor-two larger cost of deterministic classical discretization. For a compact, boundaryless $C^3$ submanifold $M\subset\mathrm{PU}(d)$ of dimension $\nu$, it constructs classical programs using $\frac{\nu}{2}\log_2(1/\varepsilon)+O(1)$ bits at diamond-distance error $\varepsilon$. A matching leading-order lower bound for arbitrary quantum programs is $c_P^*\geq\frac{\nu}{2}\log_2(1/\varepsilon)-\frac{3\nu}{2}\log_2\log_2(1/\varepsilon)-O(1)$. Thus randomized classical programs attain the optimal leading coefficient, including $(d^2-1)/2$ for all unitary channels, establishing the stated parameter-counting conjecture under these regularity assumptions. The construction covers the family by finitely many coordinate charts and randomly rounds coordinates to lattice vertices with spacing $h=\Theta(\sqrt\varepsilon)$. Unbiased rounding cancels first-order errors in the averaged channel, leaving $O(h^2)$ error and requiring $O(\varepsilon^{-\nu/2})$ labels. For an unknown target, Heisenberg-limited estimation followed by a smooth local retraction onto the family generates the program with $O(\varepsilon^{-1/2})$ queries. The lower bound combines program recycling, parallel unitary estimation, and a communication bound. The guarantees concern the averaged implemented channel, not each sampled unitary. Asymptotics hold with $d$ and the family fixed; constants depend on family geometry and need not be uniformly computable. General encoding complexity assumes access to coordinates and a retraction. A subleading $O(\log\log(1/\varepsilon))$ gap remains.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 15 pages, 3 figures