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:2606.08784

Randomized simulation of quantum channels using small ancilla

Marcin Kotowski, Michał Kotowski

quant-phSubmitted Jun 7, 2026• Announced Jun 9, 2026• 0 citations
arXivHTMLPDF

Abstract

We study the problem of implementing a quantum channel using a small ancilla with classical randomization and postselection on an output failure flag. The simulation is probabilistic, but exact conditioned on success. We prove that any unital channel on a $d$-dimensional system can be simulated with ancilla dimension $k$ and success probability $Ω(\frac{k}{\log d})$. Equivalently, every unital channel on $n$ qubits can be simulated with constant success probability using only $O(\log n)$ ancillary qubits. We show that this tradeoff is best possible by constructing a family of channels which cannot be simulated with success probability better than $O(\frac{k}{\log d})$. We also show that the class of \textit{highly noncommutative} channels, which includes random channels, admits constant-success simulation with just a single ancillary qubit. We further show that this model of simulation necessarily fails for strongly non-unital channels and discuss possible extensions involving adaptivity. On the technical side we rely on a partition-based protocol and matrix concentration inequalities, including the recent refinement of noncommutative Khintchine inequalities due to Bandeira, Boedihardjo and van Handel.

Related papers

Probabilistic nonunitary quantum computing

Colin P. Williams

In [1] Gingrich and Williams extended the standard quantum circuit model of quantum computation to include gates that perform arbitrary linear, yet non-unitary, transformations of their input state. In this paper we use this theory to construct quantum circuits that perform desired non-unitary state transformations of the sort arising in lattice-based quantum search. Such n-qubit non-unitary gates cannot be achieved deterministically, but they can be achieved probabilistically using a single ancilla. Our approach is to use the n-qubit non-unitary gate to design an (n+1)-qubit Hamiltonian that can be seen to induce a suitable conditional dynamics such that whenever the output value of the ancilla qubit is measured and found to be |O>, then the remaining (unmeasured) n qubits will contain the desired non-unitary transform of the n-qubit input state. The scheme is necessarily probabilistic because we cannot force the measurement on the ancilla qubit to return the value we want. Fortunately, however, failed attempts are found to disturb the n-qubit input state very little. This allows us to re-use the result of successive “failed” attempts until the success condition is finally attained, and we give analytic expressions for the success probability and net fidelity in this case. By using our previous method for designing a quantum circuit for an arbitrary n-qubit gate in conjunction with our new probabilistic non-unitary procedure we are able to compute an explicit quantum circuit sufficient to implement an arbitrary linear, yet non-unitary, transformation of an input pure or mixed n-qubit state, using only a single copy of the input state. This allows us to extend the repertoire of computations that may be performed on a quantum computer, and in particular, gives the first explicit construction of the quantum circuits needed to perform some of the key operations arising in quantum lattice search.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 24, 2004•8 citations

Low-Depth Random Unitaries without Ancillae

Zhenyu Du, Siyuan Cheng, Xiongfeng Ma

Random unitaries are fundamental to quantum information and many-body physics, with widespread applications ranging from quantum learning and metrology to device benchmarking. A central pursuit is to minimize the space and circuit depth required to generate them. However, existing methods for generating low-depth random unitaries rely heavily on an extensive number of ancillary qubits, imposing severe spatial overhead. In this work, we prove that random unitaries can be generated in optimal depth without ancillae. For multiplicative-error approximate $k$-designs on $n$ qubits, our circuits achieve a depth of $\widetilde{O} (k) (\log n)^{1/δ}$ on $δ$-dimensional architectures and $\widetilde{O}(k) \log \log n$ with all-to-all connectivity. Furthermore, by introducing a general exactification lemma, we lift our construction to optimal-depth exact $k$-designs, yielding an exponential resource reduction over state-of-the-art exact constructions. Our results minimize the space-time costs for a wide range of quantum protocols.

quant-pharXiv:2609.06528•Sep 8, 2026•0 citations

Discretization of quantum pure states and local random unitary channel

Dong Pyo Chi, Kabgyun Jeong

We show that a quantum channel $\mathcal{N}$ constructed by averaging over $\mathcal{O}(\log d/ε^2)$ randomly chosen unitaries gives a local $ε$-randomizing map with non-negative probability. The idea comes from a small $ε$-net construction on the higher dimensional unit sphere or quantum pure states. By exploiting the net, we analyze the concentrative phenomenon of an output reduced density matrix of the channel, and this analysis imply that there exists a local random unitary channel, with relatively small unitaries, generically.

arXiv:1002.3427•Feb 18, 2010•0 citations

Implementation of quantum measurements using classical resources and only a single ancillary qubit

Tanmay Singal, Filip B. Maciejewski, Michał Oszmaniec

Abstract We propose a scheme to implement general quantum measurements, also known as Positive Operator Valued Measures (POVMs) in dimension d using only classical resources and a single ancillary qubit. Our method is based on probabilistic implementation of d-outcome measurements which is followed by postselection of some of the received outcomes. We conjecture that success probability of our scheme is larger than a constant independent of d for all POVMs in dimension d. Crucially, this conjecture implies the possibility of realizing arbitrary nonadaptive quantum measurement protocol on d-dimensional system using a single auxiliary qubit with only a constant overhead in sampling complexity. We show that the conjecture holds for typical rank-one Haar-random POVMs in arbitrary dimensions. Furthermore, we carry out extensive numerical computations showing success probability above a constant for a variety of extremal POVMs, including SIC-POVMs in dimension up to 1299. Finally, we argue that our scheme can be favorable for experimental realization of POVMs, as noise compounding in circuits required by our scheme is typically substantially lower than in the standard scheme that directly uses Naimark’s dilation theorem.

arXiv:2104.05612•npj Quantum Information•Jul 13, 2022•18 citations

Entanglement depth and ancilla efficiency in quantum channel estimation

Javid Naikoo

We study the role of ancillary entanglement in quantum channel parameter estimation and investigate the minimal ancilla dimension required to achieve the maximum Fisher information. We introduce the $k$-ancilla Fisher information, which quantifies the optimal estimation precision achievable with input states of rank at most $k$, and derive a variational characterization in terms of a rank-constrained optimization problem. This formulation leads to a simple characterization of the minimum ancilla dimension $k^*$ required for optimal estimation, given by the minimum rank among the maximizers of the associated variational problem. We further identify sufficient conditions under which ancillary entanglement provides no advantage, including channel families admitting a fixed measure-and-prepare representation and channels satisfying a natural horizontality condition. In addition, we derive a bound on the incremental gain in Fisher information obtained by increasing the ancilla dimension under suitable structural assumptions on the optimal input states. The general results are illustrated through explicit examples, including unitary channels, qubit depolarizing and amplitude damping channels. These results provide a systematic framework for understanding and quantifying the entanglement resources required for optimal quantum channel estimation.

quant-pharXiv:2608.11042•Aug 12, 2026•0 citations

Optimality of Meta-Converse for Channel Simulation

Mario Berta, Omar Fawzi, Aadil Oufkir

We study the effect of shared non-signaling correlations for the problem of simulating a channel using noiseless communication in the one-shot setting. For classical channels, we show how to round any non-signaling-assisted simulation strategy - which exactly corresponds to the meta-converse for channel simulation - to a strategy that only uses shared randomness. For quantum channels, we round any non-signaling-assisted simulation strategy to a strategy that only uses shared entanglement. As our main result, we prove a guarantee on the ratio of success probabilities of at least$(1-\frac{-1}{\mathbf{e}})$, for both the classical and the quantum setting. We further - show this ratio to be optimal. It can be improved to$(1-\frac{1}{t})$using$o$(ln$(t)$) additional bits (qubits) of communication.

arXiv:2410.08140•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•4 citations
We study the problem of implementing a quantum channel using a small ancilla with classical randomization and postselection on an output failure flag. The simulation is probabilistic, but exact conditioned on success. We prove that any unital channel on a ddd-dimensional system can be simulated with ancilla dimension kkk and success probability Ω(klog⁡d)Ω(\frac{k}{\log d})Ω(logdk​). Equivalently, every unital channel on nnn qubits can be simulated with constant success probability using only O(log⁡n)O(\log n)O(logn) ancillary qubits. We show that this tradeoff is best possible by constructing a family of channels which cannot be simulated with success probability better than O(klog⁡d)O(\frac{k}{\log d})O(logdk​). We also show that the class of \textit{highly noncommutative} channels, which includes random channels, admits constant-success simulation with just a single ancillary qubit. We further show that this model of simulation necessarily fails for strongly non-unital channels and discuss possible extensions involving adaptivity. On the technical side we rely on a partition-based protocol and matrix concentration inequalities, including the recent refinement of noncommutative Khintchine inequalities due to Bandeira, Boedihardjo and van Handel.
In [1] Gingrich and Williams extended the standard quantum circuit model of quantum computation to include gates that perform arbitrary linear, yet non-unitary, transformations of their input state. In this paper we use this theory to construct quantum circuits that perform desired non-unitary state transformations of the sort arising in lattice-based quantum search. Such n-qubit non-unitary gates cannot be achieved deterministically, but they can be achieved probabilistically using a single ancilla. Our approach is to use the n-qubit non-unitary gate to design an (n+1)-qubit Hamiltonian that can be seen to induce a suitable conditional dynamics such that whenever the output value of the ancilla qubit is measured and found to be |O>, then the remaining (unmeasured) n qubits will contain the desired non-unitary transform of the n-qubit input state. The scheme is necessarily probabilistic because we cannot force the measurement on the ancilla qubit to return the value we want. Fortunately, however, failed attempts are found to disturb the n-qubit input state very little. This allows us to re-use the result of successive “failed” attempts until the success condition is finally attained, and we give analytic expressions for the success probability and net fidelity in this case. By using our previous method for designing a quantum circuit for an arbitrary n-qubit gate in conjunction with our new probabilistic non-unitary procedure we are able to compute an explicit quantum circuit sufficient to implement an arbitrary linear, yet non-unitary, transformation of an input pure or mixed n-qubit state, using only a single copy of the input state. This allows us to extend the repertoire of computations that may be performed on a quantum computer, and in particular, gives the first explicit construction of the quantum circuits needed to perform some of the key operations arising in quantum lattice search.
Random unitaries are fundamental to quantum information and many-body physics, with widespread applications ranging from quantum learning and metrology to device benchmarking. A central pursuit is to minimize the space and circuit depth required to generate them. However, existing methods for generating low-depth random unitaries rely heavily on an extensive number of ancillary qubits, imposing severe spatial overhead. In this work, we prove that random unitaries can be generated in optimal depth without ancillae. For multiplicative-error approximate kkk-designs on nnn qubits, our circuits achieve a depth of O~(k)(log⁡n)1/δ\widetilde{O} (k) (\log n)^{1/δ}O(k)(logn)1/δ on δδδ-dimensional architectures and O~(k)log⁡log⁡n\widetilde{O}(k) \log \log nO(k)loglogn with all-to-all connectivity. Furthermore, by introducing a general exactification lemma, we lift our construction to optimal-depth exact kkk-designs, yielding an exponential resource reduction over state-of-the-art exact constructions. Our results minimize the space-time costs for a wide range of quantum protocols.
We show that a quantum channel N\mathcal{N}N constructed by averaging over O(log⁡d/ε2)\mathcal{O}(\log d/ε^2)O(logd/ε2) randomly chosen unitaries gives a local εεε-randomizing map with non-negative probability. The idea comes from a small εεε-net construction on the higher dimensional unit sphere or quantum pure states. By exploiting the net, we analyze the concentrative phenomenon of an output reduced density matrix of the channel, and this analysis imply that there exists a local random unitary channel, with relatively small unitaries, generically.
Abstract We propose a scheme to implement general quantum measurements, also known as Positive Operator Valued Measures (POVMs) in dimension d using only classical resources and a single ancillary qubit. Our method is based on probabilistic implementation of d-outcome measurements which is followed by postselection of some of the received outcomes. We conjecture that success probability of our scheme is larger than a constant independent of d for all POVMs in dimension d. Crucially, this conjecture implies the possibility of realizing arbitrary nonadaptive quantum measurement protocol on d-dimensional system using a single auxiliary qubit with only a constant overhead in sampling complexity. We show that the conjecture holds for typical rank-one Haar-random POVMs in arbitrary dimensions. Furthermore, we carry out extensive numerical computations showing success probability above a constant for a variety of extremal POVMs, including SIC-POVMs in dimension up to 1299. Finally, we argue that our scheme can be favorable for experimental realization of POVMs, as noise compounding in circuits required by our scheme is typically substantially lower than in the standard scheme that directly uses Naimark’s dilation theorem.
We study the role of ancillary entanglement in quantum channel parameter estimation and investigate the minimal ancilla dimension required to achieve the maximum Fisher information. We introduce the kkk-ancilla Fisher information, which quantifies the optimal estimation precision achievable with input states of rank at most kkk, and derive a variational characterization in terms of a rank-constrained optimization problem. This formulation leads to a simple characterization of the minimum ancilla dimension k∗k^*k∗ required for optimal estimation, given by the minimum rank among the maximizers of the associated variational problem. We further identify sufficient conditions under which ancillary entanglement provides no advantage, including channel families admitting a fixed measure-and-prepare representation and channels satisfying a natural horizontality condition. In addition, we derive a bound on the incremental gain in Fisher information obtained by increasing the ancilla dimension under suitable structural assumptions on the optimal input states. The general results are illustrated through explicit examples, including unitary channels, qubit depolarizing and amplitude damping channels. These results provide a systematic framework for understanding and quantifying the entanglement resources required for optimal quantum channel estimation.
We study the effect of shared non-signaling correlations for the problem of simulating a channel using noiseless communication in the one-shot setting. For classical channels, we show how to round any non-signaling-assisted simulation strategy - which exactly corresponds to the meta-converse for channel simulation - to a strategy that only uses shared randomness. For quantum channels, we round any non-signaling-assisted simulation strategy to a strategy that only uses shared entanglement. As our main result, we prove a guarantee on the ratio of success probabilities of at least(1−−1e)(1-\frac{-1}{\mathbf{e}})(1−e−1​), for both the classical and the quantum setting. We further - show this ratio to be optimal. It can be improved to(1−1t)(1-\frac{1}{t})(1−t1​)usingooo(ln(t)(t)(t)) additional bits (qubits) of communication.