Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.02441

Barycentric programming: Classical realization of programs for universal quantum processors

Yutaka Hashimoto, Satoshi Yoshida, Mio Murao

quant-phSubmitted Nov 2, 2026• Announced Nov 3, 2026• 0 citations
arXivHTMLPDF

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.

No sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
15 pages, 3 figures

Related papers

Quantum and Classical Memory for Storage and Retrieval of Quantum Measurements

Filip Turoboś, Ludmiła Marcinkowska, Zbigniew Puchała

We study the persistent quantum and classical memory required for exact heralded storage and retrieval of quantum measurements. Given only black-box access to the measurement channel, we construct an exact compression of the port-based program into an outcome-type record and a quantum register, with total dimension polynomial in the query count. For every universal retrieval processor we prove the bounds $Q+C\ge\log_2 n$ and $2Q+C\ge\log_2\bigl((n-1)d^2+1\bigr)$ on the numbers $Q$ of qubits and $C$ of bits of the program, for $n$-outcome POVMs on $\mathbb{C}^d$ with $d\ge2$. For $n\ge2$, no finite classical memory removes the need for quantum memory: any such processor requires a quantum program of dimension at least $d$, at that dimension its classical alphabet must have at least $n$ symbols, and both minima are attained by a single-query protocol with success $1/d^2$. Combining direct-program compression with a converse from approximate measurement programming gives logarithmic total-memory scaling in $1/(1-p)$ as the uniform success probability $p$ approaches one, at fixed $d,n\ge2$. At fixed input dimension and target success below one, the optimal total-memory scaling is logarithmic in $n$. We also construct self-contained programs under branch-decomposition access and compare the quantum and classical costs of all constructions, including where the outcome-type record is kept: for POVMs with $n$ nonzero rank-one effects the direct program admits a purely quantum allocation whose register is never larger than that of the minimal-Naimark unitary program and which succeeds more often whenever $n>d$.

quant-pharXiv:2610.36972•Oct 28, 2026•0 citations

Quantum Programmable Reflections

Eddie Schoute, Dmitry Grinko, Yiğit Subaşı +1 more

Similar to a classical processor, which is an algorithm for reading a program and executing its instructions on input data, a universal programmable quantum processor is a fixed quantum channel that reads a quantum program $\lvertψ_{U}\rangle$ that causes the processor to approximately apply an arbitrary unitary $U$ to a quantum data register. The present work focuses on a class of simple programmable quantum processors for implementing reflection operators, i.e. $U = e^{i π\lvertψ\rangle\langleψ\rvert}$ for an arbitrary pure state $\lvertψ\rangle$ of finite dimension $d$. Unlike quantum programs that assume query access to $U$, our program takes the form of independent copies of the state to be reflected about $\lvertψ_U\rangle = \lvertψ\rangle^{\otimes n}$. We then identify the worst-case optimal algorithm among all processors of the form $\text{tr}_{\text{Program}}[V (\lvertϕ\rangle\langleϕ\rvert \otimes (\lvertψ\rangle\langleψ\rvert)^{\otimes n}) V^\dagger]$ where the algorithm $V$ is a unitary linear combination of permutations. By generalizing these algorithms to processors for arbitrary-angle rotations, $e^{i α\lvertψ\rangle\langleψ\rvert}$ for $α\in \mathbb R$, we give a construction for a universal programmable processor with better scaling in $d$. For programming reflections, we obtain a tight analytical lower bound on the program dimension by bounding the Holevo information of an ensemble of reflections applied to an entangled probe state. The lower bound makes use of a block decomposition of the uniform ensemble of reflected states with respect to irreps of the partially transposed permutation matrix algebra, and two representation-theoretic conjectures based on extensive numerical evidence.

arXiv:2411.03648•Nov 6, 2024•7 citations

Optimal Universal Programming of Unitary Gates

Yuxiang Yang, Renato Renner, Giulio Chiribella

A universal quantum processor is a device that takes as input a (quantum) program, containing an encoding of an arbitrary unitary gate, and a (quantum) data register, on which the encoded gate is applied. While no perfect universal quantum processor can exist, approximate processors have been proposed in the past two decades. A fundamental open question is how the size of the smallest quantum program scales with the approximation error. Here we answer the question, by proving a bound on the size of the program and designing a concrete protocol that attains the bound in the asymptotic limit. Our result is based on a connection between optimal programming and the Heisenberg limit of quantum metrology, and establishes an asymptotic equivalence between the tasks of programming, learning, and estimating unitary gates.

arXiv:2007.10363•Physical Review Letters•Nov 16, 2020•53 citations

Exact Virtual Channel Programming with Vanishing Excess Overhead

Mingrui Jing, Mengbo Guo, Hongshun Yao +1 more

A finite-dimensional physical processor cannot exactly program a continuous family of distinct unitary channels. We show that this obstruction becomes quantitative when the target channel is stored in a normalized Choi state and its output observables are reconstructed by sampling physical channels and classically post-processing their measurement outcomes. For arbitrary $d$-dimensional channels, we construct a target-independent exact reconstruction protocol and prove the optimal one-copy sampling overhead, which grows quadratically with system dimension. We further prove the sharp fixed-$d$ law that the excess overhead vanishes inversely with the number of identical Choi programs. The upper bound combines deterministic port-based teleportation with a quasi-decomposition that corrects its depolarizing distortion. The converse maps any low-overhead reconstruction protocol to a physical learner of unknown unitaries and uses local quantum estimation to recover the same leading coefficient. These results recast the universal no-programming obstruction as a quantitative trade-off between quantum program memory and classical sampling, with a leading cost that reflects the locally learnable unitary degrees of freedom.

quant-pharXiv:2609.01419•Sep 2, 2026•0 citations

Approximate Programmable Quantum Processors in Infinite Dimensions

Martina Gschwendtner, Andreas Winter

A universal programmable quantum processor uses program quantum states to apply an arbitrary quantum channel to an input state. We generalize the concept of a finite-dimensional programmable quantum processor to infinite dimensions assuming an energy constraint on the input and output of the target quantum channels. Upper and lower bounds for the required program dimension, to approximately implement energy-limited quantum channels, are provided. In particular, we consider the implementation of Gaussian channels. Due to their practical relevance, we investigate the resource requirements for gauge covariant Gaussian channels. Additionally, we give upper and lower bounds for the program dimension of a processor implementing all Gaussian unitary channels.

•Dec 1, 2020•0 citations

Optimal Diamond Distance Estimation for Unitary Channels

Jinge Bao, Qisheng Wang

The diamond distance between two quantum channels determines the optimal probability of distinguishing them from a single use. We give a quantum algorithm that estimates the diamond distance between two unknown $d$-dimensional unitary channels to within additive error $\varepsilon$, using $O(\sqrt{d}/\varepsilon)$ queries to the unitary channels and their inverses. The query complexity is optimal, as it matches the lower bound due to Jeon and Oh (npj Quantum Inf. 2026).

quant-pharXiv:2610.40623•Oct 30, 2026•0 citations
A programmable quantum processor implements a target unitary using information stored in a classical or quantum program register. For arbitrary unitaries in SU(d)\mathrm{SU}(d)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/ε)+O(1)(ν/2)\log_2(1/\varepsilon)+O(1)(ν/2)log2​(1/ε)+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/ε)(ν/2+o(1))\log_2(1/\varepsilon)(ν/2+o(1))log2​(1/ε) without requiring coherent quantum memory.
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 C3C^3C3 submanifold M⊂PU(d)M\subset\mathrm{PU}(d)M⊂PU(d) of dimension ν\nuν, it constructs classical programs using ν2log⁡2(1/ε)+O(1)\frac{\nu}{2}\log_2(1/\varepsilon)+O(1)2ν​log2​(1/ε)+O(1) bits at diamond-distance error ε\varepsilonε. A matching leading-order lower bound for arbitrary quantum programs is cP∗≥ν2log⁡2(1/ε)−3ν2log⁡2log⁡2(1/ε)−O(1)c_P^*\geq\frac{\nu}{2}\log_2(1/\varepsilon)-\frac{3\nu}{2}\log_2\log_2(1/\varepsilon)-O(1)cP∗​≥2ν​log2​(1/ε)−23ν​log2​log2​(1/ε)−O(1). Thus randomized classical programs attain the optimal leading coefficient, including (d2−1)/2(d^2-1)/2(d2−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=Θ(ε)h=\Theta(\sqrt\varepsilon)h=Θ(ε​). Unbiased rounding cancels first-order errors in the averaged channel, leaving O(h2)O(h^2)O(h2) error and requiring O(ε−ν/2)O(\varepsilon^{-\nu/2})O(ε−ν/2) labels. For an unknown target, Heisenberg-limited estimation followed by a smooth local retraction onto the family generates the program with O(ε−1/2)O(\varepsilon^{-1/2})O(ε−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 ddd 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/ε))O(\log\log(1/\varepsilon))O(loglog(1/ε)) gap remains.
We study the persistent quantum and classical memory required for exact heralded storage and retrieval of quantum measurements. Given only black-box access to the measurement channel, we construct an exact compression of the port-based program into an outcome-type record and a quantum register, with total dimension polynomial in the query count. For every universal retrieval processor we prove the bounds Q+C≥log⁡2nQ+C\ge\log_2 nQ+C≥log2​n and 2Q+C≥log⁡2((n−1)d2+1)2Q+C\ge\log_2\bigl((n-1)d^2+1\bigr)2Q+C≥log2​((n−1)d2+1) on the numbers QQQ of qubits and CCC of bits of the program, for nnn-outcome POVMs on Cd\mathbb{C}^dCd with d≥2d\ge2d≥2. For n≥2n\ge2n≥2, no finite classical memory removes the need for quantum memory: any such processor requires a quantum program of dimension at least ddd, at that dimension its classical alphabet must have at least nnn symbols, and both minima are attained by a single-query protocol with success 1/d21/d^21/d2. Combining direct-program compression with a converse from approximate measurement programming gives logarithmic total-memory scaling in 1/(1−p)1/(1-p)1/(1−p) as the uniform success probability ppp approaches one, at fixed d,n≥2d,n\ge2d,n≥2. At fixed input dimension and target success below one, the optimal total-memory scaling is logarithmic in nnn. We also construct self-contained programs under branch-decomposition access and compare the quantum and classical costs of all constructions, including where the outcome-type record is kept: for POVMs with nnn nonzero rank-one effects the direct program admits a purely quantum allocation whose register is never larger than that of the minimal-Naimark unitary program and which succeeds more often whenever n>dn>dn>d.
Similar to a classical processor, which is an algorithm for reading a program and executing its instructions on input data, a universal programmable quantum processor is a fixed quantum channel that reads a quantum program ∣ψU⟩\lvertψ_{U}\rangle∣ψU​⟩ that causes the processor to approximately apply an arbitrary unitary UUU to a quantum data register. The present work focuses on a class of simple programmable quantum processors for implementing reflection operators, i.e. U=eiπ∣ψ⟩⟨ψ∣U = e^{i π\lvertψ\rangle\langleψ\rvert}U=eiπ∣ψ⟩⟨ψ∣ for an arbitrary pure state ∣ψ⟩\lvertψ\rangle∣ψ⟩ of finite dimension ddd. Unlike quantum programs that assume query access to UUU, our program takes the form of independent copies of the state to be reflected about ∣ψU⟩=∣ψ⟩⊗n\lvertψ_U\rangle = \lvertψ\rangle^{\otimes n}∣ψU​⟩=∣ψ⟩⊗n. We then identify the worst-case optimal algorithm among all processors of the form trProgram[V(∣ϕ⟩⟨ϕ∣⊗(∣ψ⟩⟨ψ∣)⊗n)V†]\text{tr}_{\text{Program}}[V (\lvertϕ\rangle\langleϕ\rvert \otimes (\lvertψ\rangle\langleψ\rvert)^{\otimes n}) V^\dagger]trProgram​[V(∣ϕ⟩⟨ϕ∣⊗(∣ψ⟩⟨ψ∣)⊗n)V†] where the algorithm VVV is a unitary linear combination of permutations. By generalizing these algorithms to processors for arbitrary-angle rotations, eiα∣ψ⟩⟨ψ∣e^{i α\lvertψ\rangle\langleψ\rvert}eiα∣ψ⟩⟨ψ∣ for α∈Rα\in \mathbb Rα∈R, we give a construction for a universal programmable processor with better scaling in ddd. For programming reflections, we obtain a tight analytical lower bound on the program dimension by bounding the Holevo information of an ensemble of reflections applied to an entangled probe state. The lower bound makes use of a block decomposition of the uniform ensemble of reflected states with respect to irreps of the partially transposed permutation matrix algebra, and two representation-theoretic conjectures based on extensive numerical evidence.
A universal quantum processor is a device that takes as input a (quantum) program, containing an encoding of an arbitrary unitary gate, and a (quantum) data register, on which the encoded gate is applied. While no perfect universal quantum processor can exist, approximate processors have been proposed in the past two decades. A fundamental open question is how the size of the smallest quantum program scales with the approximation error. Here we answer the question, by proving a bound on the size of the program and designing a concrete protocol that attains the bound in the asymptotic limit. Our result is based on a connection between optimal programming and the Heisenberg limit of quantum metrology, and establishes an asymptotic equivalence between the tasks of programming, learning, and estimating unitary gates.
A finite-dimensional physical processor cannot exactly program a continuous family of distinct unitary channels. We show that this obstruction becomes quantitative when the target channel is stored in a normalized Choi state and its output observables are reconstructed by sampling physical channels and classically post-processing their measurement outcomes. For arbitrary ddd-dimensional channels, we construct a target-independent exact reconstruction protocol and prove the optimal one-copy sampling overhead, which grows quadratically with system dimension. We further prove the sharp fixed-ddd law that the excess overhead vanishes inversely with the number of identical Choi programs. The upper bound combines deterministic port-based teleportation with a quasi-decomposition that corrects its depolarizing distortion. The converse maps any low-overhead reconstruction protocol to a physical learner of unknown unitaries and uses local quantum estimation to recover the same leading coefficient. These results recast the universal no-programming obstruction as a quantitative trade-off between quantum program memory and classical sampling, with a leading cost that reflects the locally learnable unitary degrees of freedom.
A universal programmable quantum processor uses program quantum states to apply an arbitrary quantum channel to an input state. We generalize the concept of a finite-dimensional programmable quantum processor to infinite dimensions assuming an energy constraint on the input and output of the target quantum channels. Upper and lower bounds for the required program dimension, to approximately implement energy-limited quantum channels, are provided. In particular, we consider the implementation of Gaussian channels. Due to their practical relevance, we investigate the resource requirements for gauge covariant Gaussian channels. Additionally, we give upper and lower bounds for the program dimension of a processor implementing all Gaussian unitary channels.
The diamond distance between two quantum channels determines the optimal probability of distinguishing them from a single use. We give a quantum algorithm that estimates the diamond distance between two unknown ddd-dimensional unitary channels to within additive error ε\varepsilonε, using O(d/ε)O(\sqrt{d}/\varepsilon)O(d​/ε) queries to the unitary channels and their inverses. The query complexity is optimal, as it matches the lower bound due to Jeon and Oh (npj Quantum Inf. 2026).