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:1909.01366 · Physical Review A

Probabilistic exact universal quantum circuits for transforming unitary operations

Marco Túlio Quintino, Qingxiuxiong Dong, Atsushi Shimbo, Akihito Soeda, Mio Murao

Published Dec 30, 2019• 49 citations
arXivHTMLPDF

Abstract

This paper addresses the problem of designing universal quantum circuits to transform $k$ uses of a $d$-dimensional unitary input operation into a unitary output operation in a probabilistic heralded manner. Three classes of protocols are considered, parallel circuits, where the input operations can be performed simultaneously, adaptive circuits, where sequential uses of the input operations are allowed, and general protocols, where the use of the input operations may be performed without a definite causal order. For these three classes, we develop a systematic semidefinite programming approach that finds a circuit which obtains the desired transformation with the maximal success probability. We then analyze in detail three particular transformations: unitary transposition, unitary complex conjugation, and unitary inversion. For unitary transposition and unitary inverse, we prove that for any fixed dimension $d$, adaptive circuits have an exponential improvement in terms of uses $k$ when compared to parallel ones. For unitary complex conjugation and unitary inversion we prove that if the number of uses $k$ is strictly smaller than $d\ensuremath{-}1$, the probability of success is necessarily zero. We also discuss the advantage of indefinite causal order protocols over causal ones and introduce the concept of delayed input-state quantum circuits.

DOI
10.1103/physreva.100.062339

Related papers

Reversing Unknown Quantum Transformations: Universal Quantum Circuit for Inverting General Unitary Operations

Marco Túlio Quintino, Qingxiuxiong Dong, Atsushi Shimbo +2 more

Given a quantum gate implementing a d-dimensional unitary operation U_{d}, without any specific description but d, and permitted to use k times, we present a universal probabilistic heralded quantum circuit that implements the exact inverse U_{d}^{-1}, whose failure probability decays exponentially in k. The protocol employs an adaptive strategy, proven necessary for the exponential performance. It requires that k≥d-1, proven necessary for the exact implementation of U_{d}^{-1} with quantum circuits. Moreover, even when quantum circuits with indefinite causal order are allowed, k≥d-1 uses are required. We then present a finite set of linear and positive semidefinite constraints characterizing universal unitary inversion protocols and formulate a convex optimization problem whose solution is the maximum success probability for given k and d. The optimal values are computed using semidefinite programing solvers for k≤3 when d=2 and k≤2 for d=3. With this numerical approach we show for the first time that indefinite causal order circuits provide an advantage over causally ordered ones in a task involving multiple uses of the same unitary operation.

arXiv:1810.06944•Physical Review Letters•Nov 21, 2019•82 citations

Reversing unknown quantum transformations: A universal protocol for inverting general unitary operations

Marco Túlio Quintino, Qingxiuxiong Dong, Atsushi Shimbo +2 more

Given a quantum gate implementing a $d$-dimensional unitary operation $U_d$, without any specific description but $d$, and permitted to use $k$ times, we present a universal probabilistic heralded quantum circuit that implements the exact inverse $U_d^{-1}$, whose failure probability decays, exponentially in $k$. The protocol employs an adaptive strategy, proven necessary for the exponential performance. It requires $k\geq d-1$, proven necessary for exact implementation of $U_d^{-1}$ with quantum circuits. Moreover, even when quantum circuits with indefinite causal order are allowed, $k\geq d-1$ uses are required. We then present a finite set of linear and positive semidefinite constraints characterizing universal unitary inversion protocols and formulate a convex optimization problem whose solution is the maximum success probability for given $k$ and $d$. The optimal values are computed using semidefinite programming solvers for $k\leq 3$ when $d=2$ and $k\leq 2$ for $d=3$. With this numerical approach we show for the first time that indefinite causal order circuits provide an advantage over causally ordered ones in a task involving multiple uses of the same unitary operation.

•Oct 16, 2018•2 citations

Deterministic transformations between unitary operations: Exponential advantage with adaptive quantum circuits and the power of indefinite causality

Marco Túlio Quintino, Daniel Ebler

This work analyses the performance of quantum circuits and general processes to transform k uses of an arbitrary unitary operation U into another unitary operation f(U) . When the desired function f a homomorphism, i.e., f(UV)=f(U)f(V) , it is known that optimal average fidelity is attainable by parallel circuits and indefinite causality does not provide any advantage. Here we show that the situation changes dramatically when considering anti-homomorphisms, i.e., f(UV)=f(V)f(U) . In particular, we prove that when f is an anti-homomorphism, sequential circuits could exponentially outperform parallel ones and processes with indefinite causal order could outperform sequential ones. We presented explicit constructions on how to obtain such advantages for the unitary inversion task f(U)=U−1 and the unitary transposition task f(U)=UT . We also stablish a one-to-one connection between the problem of unitary estimation and parallel unitary transposition, allowing one to easily translate results from one field to the other. Finally, we apply our results to several concrete problem instances and present a method based on computer-assisted proofs to show optimality.

arXiv:2109.08202•Quantum•Mar 31, 2022•26 citations

Random dilation superchannel

Satoshi Yoshida, Ryotaro Niwa, Takeru Utsumi +2 more

We present a quantum circuit that implements the random dilation superchannel, transforming parallel queries of an unknown quantum channel into the same number of parallel queries of a randomly chosen dilation isometry of the input channel. This is a natural generalization of the random purification channel, that transforms copies of an unknown mixed state to copies of a randomly chosen purification state. The circuit complexity of our construction is $O(\mathrm{poly}(n, \log d_I, \log d_O))$, where $n$ is the number of queries and $d_I$ and $d_O$ are the input and output dimensions of the input channel, respectively. This random dilation superchannel is extended to the sequential queries approximately, by transforming the parallel random dilation isometry into sequential random dilation unitaries with $O(\mathrm{poly}(d_I))$ overhead in the number of queries. We also show that our results can be further extended to the case of quantum superchannels. On the other hand, we show a no-go theorem on the exact random dilation of sequential queries with $o(\mathrm{poly}(\min\{d_I, d_O\}))$ query overhead, showcasing a fundamental difference between the parallel and sequential cases. As an application, we show an efficient storage-and-retrieval of an unknown quantum channel, which improves the program cost exponentially in the retrieval error $\varepsilon$. For the case where the Kraus rank $r$ is the least possible (i.e., $r = d_I/d_O$), we show quantum circuits that transform $n$ parallel queries of an unknown quantum channel $Λ$ to $Θ(n^α)$ parallel queries of $Λ$ for any $α<2$ approximately, and implement its Petz recovery map for the maximally mixed reference state probabilistically and exactly.

quant-pharXiv:2512.21260•Dec 25, 2025•0 citations

Reversing Unknown Qubit-Unitary Operation, Deterministically and Exactly

Satoshi Yoshida, Akihito Soeda, Mio Murao

We report a deterministic and exact protocol to reverse any unknown qubit-unitary operation, which simulates the time inversion of a closed qubit system. To avoid known no-go results on universal deterministic exact unitary inversion, we consider the most general class of protocols transforming unknown unitary operations within the quantum circuit model, where the input unitary operation is called multiple times in sequence and fixed quantum circuits are inserted between the calls. In the proposed protocol, the input qubit-unitary operation is called 4 times to achieve the inverse operation, and the output state in an auxiliary system can be reused as a catalyst state in another run of the unitary inversion. We also present the simplification of the semidefinite programming for searching the optimal deterministic unitary inversion protocol for an arbitrary dimension presented by M. T. Quintino and D. Ebler [Quantum 6, 679 (2022)2521-327X10.22331/q-2022-03-31-679]. We show a method to reduce the large search space representing all possible protocols, which provides a useful tool for analyzing higher-order quantum transformations for unitary operations.

arXiv:2209.02907•Physical Review Letters•Sep 19, 2023•26 citations

Universal construction of decoders from encoding black boxes

Satoshi Yoshida, Akihito Soeda, Mio Murao

Isometry operations encode the quantum information of the input system to a larger output system, while the corresponding decoding operation would be an inverse operation of the encoding isometry operation. Given an encoding operation as a black box from a d -dimensional system to a D -dimensional system, we propose a universal protocol for isometry inversion that constructs a decoder from multiple calls of the encoding operation. This is a probabilistic but exact protocol whose success probability is independent of D . For a qubit ( d=2 ) encoded in n qubits, our protocol achieves an exponential improvement over any tomography-based or unitary-embedding method, which cannot avoid D -dependence. We present a quantum operation that converts multiple parallel calls of any given isometry operation to random parallelized unitary operations, each of dimension d . Applied to our setup, it universally compresses the encoded quantum information to a D -independent space, while keeping the initial quantum information intact. This compressing operation is combined with a unitary inversion protocol to complete the isometry inversion. We also discover a fundamental difference between our isometry inversion protocol and the known unitary inversion protocols by analyzing isometry complex conjugation and isometry transposition. General protocols including indefinite causal order are searched using semidefinite programming for any improvement in the success probability over the parallel protocols. We find a sequential "success-or-draw" protocol of universal isometry inversion for d=2 and D=3 , thus whose success probability exponentially improves over parallel protocols in the number of calls of the input isometry operation for the said case.

arXiv:2110.00258•Quantum•Mar 20, 2023•8 citations
This paper addresses the problem of designing universal quantum circuits to transform kkk uses of a ddd-dimensional unitary input operation into a unitary output operation in a probabilistic heralded manner. Three classes of protocols are considered, parallel circuits, where the input operations can be performed simultaneously, adaptive circuits, where sequential uses of the input operations are allowed, and general protocols, where the use of the input operations may be performed without a definite causal order. For these three classes, we develop a systematic semidefinite programming approach that finds a circuit which obtains the desired transformation with the maximal success probability. We then analyze in detail three particular transformations: unitary transposition, unitary complex conjugation, and unitary inversion. For unitary transposition and unitary inverse, we prove that for any fixed dimension ddd, adaptive circuits have an exponential improvement in terms of uses kkk when compared to parallel ones. For unitary complex conjugation and unitary inversion we prove that if the number of uses kkk is strictly smaller than d\ensuremath−1d\ensuremath{-}1d\ensuremath−1, the probability of success is necessarily zero. We also discuss the advantage of indefinite causal order protocols over causal ones and introduce the concept of delayed input-state quantum circuits.
Given a quantum gate implementing a d-dimensional unitary operation U_{d}, without any specific description but d, and permitted to use k times, we present a universal probabilistic heralded quantum circuit that implements the exact inverse U_{d}^{-1}, whose failure probability decays exponentially in k. The protocol employs an adaptive strategy, proven necessary for the exponential performance. It requires that k≥d-1, proven necessary for the exact implementation of U_{d}^{-1} with quantum circuits. Moreover, even when quantum circuits with indefinite causal order are allowed, k≥d-1 uses are required. We then present a finite set of linear and positive semidefinite constraints characterizing universal unitary inversion protocols and formulate a convex optimization problem whose solution is the maximum success probability for given k and d. The optimal values are computed using semidefinite programing solvers for k≤3 when d=2 and k≤2 for d=3. With this numerical approach we show for the first time that indefinite causal order circuits provide an advantage over causally ordered ones in a task involving multiple uses of the same unitary operation.
Given a quantum gate implementing a ddd-dimensional unitary operation UdU_dUd​, without any specific description but ddd, and permitted to use kkk times, we present a universal probabilistic heralded quantum circuit that implements the exact inverse Ud−1U_d^{-1}Ud−1​, whose failure probability decays, exponentially in kkk. The protocol employs an adaptive strategy, proven necessary for the exponential performance. It requires k≥d−1k\geq d-1k≥d−1, proven necessary for exact implementation of Ud−1U_d^{-1}Ud−1​ with quantum circuits. Moreover, even when quantum circuits with indefinite causal order are allowed, k≥d−1k\geq d-1k≥d−1 uses are required. We then present a finite set of linear and positive semidefinite constraints characterizing universal unitary inversion protocols and formulate a convex optimization problem whose solution is the maximum success probability for given kkk and ddd. The optimal values are computed using semidefinite programming solvers for k≤3k\leq 3k≤3 when d=2d=2d=2 and k≤2k\leq 2k≤2 for d=3d=3d=3. With this numerical approach we show for the first time that indefinite causal order circuits provide an advantage over causally ordered ones in a task involving multiple uses of the same unitary operation.
This work analyses the performance of quantum circuits and general processes to transform k uses of an arbitrary unitary operation U into another unitary operation f(U) . When the desired function f a homomorphism, i.e., f(UV)=f(U)f(V) , it is known that optimal average fidelity is attainable by parallel circuits and indefinite causality does not provide any advantage. Here we show that the situation changes dramatically when considering anti-homomorphisms, i.e., f(UV)=f(V)f(U) . In particular, we prove that when f is an anti-homomorphism, sequential circuits could exponentially outperform parallel ones and processes with indefinite causal order could outperform sequential ones. We presented explicit constructions on how to obtain such advantages for the unitary inversion task f(U)=U−1 and the unitary transposition task f(U)=UT . We also stablish a one-to-one connection between the problem of unitary estimation and parallel unitary transposition, allowing one to easily translate results from one field to the other. Finally, we apply our results to several concrete problem instances and present a method based on computer-assisted proofs to show optimality.
We present a quantum circuit that implements the random dilation superchannel, transforming parallel queries of an unknown quantum channel into the same number of parallel queries of a randomly chosen dilation isometry of the input channel. This is a natural generalization of the random purification channel, that transforms copies of an unknown mixed state to copies of a randomly chosen purification state. The circuit complexity of our construction is O(poly(n,log⁡dI,log⁡dO))O(\mathrm{poly}(n, \log d_I, \log d_O))O(poly(n,logdI​,logdO​)), where nnn is the number of queries and dId_IdI​ and dOd_OdO​ are the input and output dimensions of the input channel, respectively. This random dilation superchannel is extended to the sequential queries approximately, by transforming the parallel random dilation isometry into sequential random dilation unitaries with O(poly(dI))O(\mathrm{poly}(d_I))O(poly(dI​)) overhead in the number of queries. We also show that our results can be further extended to the case of quantum superchannels. On the other hand, we show a no-go theorem on the exact random dilation of sequential queries with o(poly(min⁡{dI,dO}))o(\mathrm{poly}(\min\{d_I, d_O\}))o(poly(min{dI​,dO​})) query overhead, showcasing a fundamental difference between the parallel and sequential cases. As an application, we show an efficient storage-and-retrieval of an unknown quantum channel, which improves the program cost exponentially in the retrieval error ε\varepsilonε. For the case where the Kraus rank rrr is the least possible (i.e., r=dI/dOr = d_I/d_Or=dI​/dO​), we show quantum circuits that transform nnn parallel queries of an unknown quantum channel ΛΛΛ to Θ(nα)Θ(n^α)Θ(nα) parallel queries of ΛΛΛ for any α<2α<2α<2 approximately, and implement its Petz recovery map for the maximally mixed reference state probabilistically and exactly.
We report a deterministic and exact protocol to reverse any unknown qubit-unitary operation, which simulates the time inversion of a closed qubit system. To avoid known no-go results on universal deterministic exact unitary inversion, we consider the most general class of protocols transforming unknown unitary operations within the quantum circuit model, where the input unitary operation is called multiple times in sequence and fixed quantum circuits are inserted between the calls. In the proposed protocol, the input qubit-unitary operation is called 4 times to achieve the inverse operation, and the output state in an auxiliary system can be reused as a catalyst state in another run of the unitary inversion. We also present the simplification of the semidefinite programming for searching the optimal deterministic unitary inversion protocol for an arbitrary dimension presented by M. T. Quintino and D. Ebler [Quantum 6, 679 (2022)2521-327X10.22331/q-2022-03-31-679]. We show a method to reduce the large search space representing all possible protocols, which provides a useful tool for analyzing higher-order quantum transformations for unitary operations.
Isometry operations encode the quantum information of the input system to a larger output system, while the corresponding decoding operation would be an inverse operation of the encoding isometry operation. Given an encoding operation as a black box from a d -dimensional system to a D -dimensional system, we propose a universal protocol for isometry inversion that constructs a decoder from multiple calls of the encoding operation. This is a probabilistic but exact protocol whose success probability is independent of D . For a qubit ( d=2 ) encoded in n qubits, our protocol achieves an exponential improvement over any tomography-based or unitary-embedding method, which cannot avoid D -dependence. We present a quantum operation that converts multiple parallel calls of any given isometry operation to random parallelized unitary operations, each of dimension d . Applied to our setup, it universally compresses the encoded quantum information to a D -independent space, while keeping the initial quantum information intact. This compressing operation is combined with a unitary inversion protocol to complete the isometry inversion. We also discover a fundamental difference between our isometry inversion protocol and the known unitary inversion protocols by analyzing isometry complex conjugation and isometry transposition. General protocols including indefinite causal order are searched using semidefinite programming for any improvement in the success probability over the parallel protocols. We find a sequential "success-or-draw" protocol of universal isometry inversion for d=2 and D=3 , thus whose success probability exponentially improves over parallel protocols in the number of calls of the input isometry operation for the said case.