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:2206.00107 · IEEE Transactions on Information Theory

Optimal Universal Quantum Circuits for Unitary Complex Conjugation

Daniel Ebler, Michał Horodecki, Marcin Marciniak, Tomasz Młynik, Marco Túlio Quintino, Michał Studziński

Published Mar 31, 2023• 25 citations
arXivHTMLPDF

Abstract

Let$U_{d}$be a unitary operator representing an arbitrary$d$-dimensional unitary quantum operation. This work presents optimal quantum circuits for transforming a number$k$of calls of$U_{d}$into its complex conjugate$\overline {U_{d}}$. Our circuits admit a parallel implementation and are proven to be optimal for any$k$and$d$with an average fidelity of$\left \langle{ {F}}\right \rangle =\frac {k+1}{d(d-k)}$. Optimality is shown for average fidelity, robustness to noise, and other standard figures of merit. This extends previous works which considered the scenario of a single call ($k=1$) of the operation$U_{d}$, and the special case of$k=d-1$calls. We then show that our results encompass optimal transformations from$k$calls of$U_{d}$to$f(U_{d})$for any arbitrary homomorphism$f$from the group of$d$-dimensional unitary operators to itself, since complex conjugation is the only non-trivial automorphism on the group of unitary operators. Finally, we apply our optimal complex conjugation implementation to design a probabilistic circuit for reversing arbitrary quantum evolutions.

DOI
10.1109/tit.2023.3263771

Related papers

Probabilistic exact universal quantum circuits for transforming unitary operations

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

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.

arXiv:1909.01366•Physical Review A•Dec 30, 2019•73 citations

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•108 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•47 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•45 citations

On the Hardness of Approximate Quantum Circuit Membership and Optimization

Adam Husted Kjelstrøm, Jaco van de Pol, Andreas Pavlogiannis

Quantum circuit optimization is an indispensable component of the quantum software stack, used to reduce noise, maximize performance, alleviate costs of quantum error correction, or target specific hardware. A related problem is approximate membership: for a fixed set of unitaries $S$, decide whether a given circuit $C$ is within distance $\varepsilon$ of a unitary in $S$ under some metric $m$. Membership is a special case of optimization, where $S$ is a set of unitaries implementable at no cost (e.g., with noise-minimal circuits, or without magic states). Janzing, Wocjan, and Beth (Int. J. Quantum Inf., 2005) showed that, for the operator metric, the case $S=\{I\}$ (approximate identity) is QMA-complete when $C$ is promised to be either close to the identity or far from it. We generalize this setting in three directions: (i) promise-free inputs, (ii) besides $S=\{I\}$, sets $S$ containing only Clifford unitaries, or only generalized permutation matrices (i.e., no superposition), and (iii) the trace-based, spectral, and operator metrics. We show that, in all cases, approximate membership is PP-hard for wide ranges of $\varepsilon$, provided $C$'s gate-set can implement Clifford+T, as the gate-sets of standard hardware do. If $S=\{I\}$, or if $S$ contains only generalized permutation matrices, $I\in S$, and $m$ is a trace-based distance, PP-hardness holds for all non-trivial $\varepsilon$. If $S=\{I\}$ and $m$ is a trace-based distance, PP-hardness holds even for circuits over classical-reversible gate-sets. Our results indicate that approximate membership is harder over promise-free inputs than the QMA-complete promise version, and that this hardness persists across quantum resources (any gates, non-Clifford, superposition) and distance metrics. They directly imply PP-hardness of circuit optimization when minimizing total, non-Clifford, or superposition gate depth or count.

quant-pharXiv:2611.04381•Nov 4, 2026•0 citations

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•9 citations
LetUdU_{d}Ud​be a unitary operator representing an arbitraryddd-dimensional unitary quantum operation. This work presents optimal quantum circuits for transforming a numberkkkof calls ofUdU_{d}Ud​into its complex conjugateUd‾\overline {U_{d}}Ud​​. Our circuits admit a parallel implementation and are proven to be optimal for anykkkanddddwith an average fidelity of⟨F⟩=k+1d(d−k)\left \langle{ {F}}\right \rangle =\frac {k+1}{d(d-k)}⟨F⟩=d(d−k)k+1​. Optimality is shown for average fidelity, robustness to noise, and other standard figures of merit. This extends previous works which considered the scenario of a single call (k=1k=1k=1) of the operationUdU_{d}Ud​, and the special case ofk=d−1k=d-1k=d−1calls. We then show that our results encompass optimal transformations fromkkkcalls ofUdU_{d}Ud​tof(Ud)f(U_{d})f(Ud​)for any arbitrary homomorphismffffrom the group ofddd-dimensional unitary operators to itself, since complex conjugation is the only non-trivial automorphism on the group of unitary operators. Finally, we apply our optimal complex conjugation implementation to design a probabilistic circuit for reversing arbitrary quantum evolutions.
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{-}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.
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.
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.
Quantum circuit optimization is an indispensable component of the quantum software stack, used to reduce noise, maximize performance, alleviate costs of quantum error correction, or target specific hardware. A related problem is approximate membership: for a fixed set of unitaries SSS, decide whether a given circuit CCC is within distance ε\varepsilonε of a unitary in SSS under some metric mmm. Membership is a special case of optimization, where SSS is a set of unitaries implementable at no cost (e.g., with noise-minimal circuits, or without magic states). Janzing, Wocjan, and Beth (Int. J. Quantum Inf., 2005) showed that, for the operator metric, the case S={I}S=\{I\}S={I} (approximate identity) is QMA-complete when CCC is promised to be either close to the identity or far from it. We generalize this setting in three directions: (i) promise-free inputs, (ii) besides S={I}S=\{I\}S={I}, sets SSS containing only Clifford unitaries, or only generalized permutation matrices (i.e., no superposition), and (iii) the trace-based, spectral, and operator metrics. We show that, in all cases, approximate membership is PP-hard for wide ranges of ε\varepsilonε, provided CCC's gate-set can implement Clifford+T, as the gate-sets of standard hardware do. If S={I}S=\{I\}S={I}, or if SSS contains only generalized permutation matrices, I∈SI\in SI∈S, and mmm is a trace-based distance, PP-hardness holds for all non-trivial ε\varepsilonε. If S={I}S=\{I\}S={I} and mmm is a trace-based distance, PP-hardness holds even for circuits over classical-reversible gate-sets. Our results indicate that approximate membership is harder over promise-free inputs than the QMA-complete promise version, and that this hardness persists across quantum resources (any gates, non-Clifford, superposition) and distance metrics. They directly imply PP-hardness of circuit optimization when minimizing total, non-Clifford, or superposition gate depth or count.
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.