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

Optimal transducers using symmetries

Benoît Dubus, Julien Ladeuze, Jérémie Roland

quant-phcs.CCSubmitted Oct 1, 2026• Announced Oct 2, 2026• 0 citations
arXivHTMLPDF

Abstract

Transducers (Belovs, Jeffery and Yolcu, 2024) are a quantum computing framework describing a quantum algorithm as a unitary converting an input state into a target state using a catalyst, an auxiliary vector that is left unchanged. They are a powerful tool in quantum algorithm design, especially in the context of quantum query complexity: feasible points of the (dual) adversary semidefinite program directly translate into transducers and the optimal transduction complexity is equal to the adversary bound, i.e. the Las Vegas complexity, which is known to characterize bounded-error quantum query complexity. Moreover, contrary to bounded-error algorithms, transducers compose exactly, which limits overheads due to controlling errors in algorithms constructed by composition. Constructing efficient, let alone optimal, transducers in terms of quantum query complexity nevertheless remains a hard task since it still requires solving the adversary SDP and constructing the unitary to obtain an explicit algorithm. In this paper, we show how using the symmetry group of state-conversion problems simplifies both steps. First, using a symmetrization argument, we prove an optimal catalyst can always be chosen covariant under a representation of the symmetry group. Second, we prove that the transducer intertwines two different representations of the group and can thus be chosen block diagonal in the isotypic decomposition of the Hilbert space. Using those methods, we then derive optimal transducers, with optimal constants, for different widely used quantum algorithmic primitives, such as unstructured search, amplitude amplification and amplitude estimation. Our approach extends previous work on the use of representation theory to compute adversary lower bounds (Høyer, Lee, and {\v S}palek, 2007; Ambainis, Magnin, Roetteler and Roland, 2011) to the systematic construction of optimal algorithms.

AI Summary

The paper studies how symmetries can simplify the construction of query-optimal quantum transducers: unitaries that convert input states to target states while returning an auxiliary catalyst unchanged. The objective is the worst-case squared catalyst norm, equal to the state-conversion adversary bound, rather than the number of queries in a fixed-length bounded-error algorithm. For state-conversion problems with finite or compact Lie symmetry groups, it develops a symmetrization procedure that produces weakly covariant catalysts without increasing cost. Stabilizer invariance then restricts the catalyst space. The input-independent transducer is shown to intertwine the input-side and output-side representations on the relevant state spans, enabling an isotypic block decomposition. Strong covariance, which fixes a trivial workspace representation, is not generally sufficient: examples show both infeasibility and suboptimality. Applications give exact optimal transduction costs $W=\sqrt{(N-M)/(4M)}$ for preparing a uniform superposition over marked items when their number is either $M$ or at least $M$, and $W=\sqrt{1-\varepsilon^2}/(2\varepsilon)$ for amplitude amplification with overlap either $\varepsilon$ or at least $\varepsilon$. Covariance reduces catalyst optimization to small problems; matching lower bounds establish optimality. For translation-invariant, periodic amplitude-estimation state conversion, the cost is $\sum_{n\in2\mathbb Z+1}|\hat h_n|$, where $h(\omega)=(1-g(\omega))/(2\sin\omega)$ and $g$ is the target overlap kernel. The analysis concerns query cost, not implementation time or space. Some constructions require infinite-dimensional workspaces; finite-dimensional realization or truncation, including its error–space trade-offs, remains open.

No sign of AI-generated textAI use disclosedUnclear writing
In this paper, AI was used for technical steps in different proofs, to find the counter-example to strong covariance, to generate the code for figures and for mathematical and language verifications.

Error found: The amplitude-estimation derivation incorrectly assumes that a continuous periodic target Gram kernel makes (1−g(ω))/(2 sin ω) continuously extendible, leaving allowed infinite-complexity cases untreated. The cyclic-scalar-oracle example admits an explicit strongly covariant feasible catalyst because its stated N-dimensional oracle register allows nonscalar symmetry representations, contradicting the example's proposition.

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

Comments
39 pages, 6 figures

Related papers

Taming Quantum Time Complexity

Aleksandrs Belovs, Stacey Jeffery, Duyal Yolcu

Quantum query complexity has several nice properties with respect to composition. First, bounded-error quantum query algorithms can be composed without incurring log factors through error reduction e x a c t n e s s . Second, through careful accounting t h r i f t i n e s s , the total query complexity is smaller if subroutines are mostly run on cheaper inputs -- a property that is much less obvious in quantum algorithms than in their classical counterparts. While these properties were previously seen through the model of span programs (alternatively, the dual adversary bound), a recent work by two of the authors (Belovs, Yolcu 2023) showed how to achieve these benefits without converting to span programs, by defining quantum Las Vegas query complexity . Independently, recent works, including by one of the authors (Jeffery 2022), have worked towards bringing thriftiness to the more practically significant setting of quantum t i m e complexity.In this work, we show how to achieve both exactness and thriftiness in the setting of time complexity. We generalize the quantum subroutine composition results of Jeffery 2022 so that, in particular, no error reduction is needed. We give a time complexity version of the well-known result in quantum query complexity, Q ( f ∘ g ) = O ( Q ( f ) ⋅ Q ( g ) ) , without log factors.We achieve this by employing a novel approach to the design of quantum algorithms based on what we call t r a n s d u c e r s , and which we think is of large independent interest. While a span program is a completely different computational model, a transducer is a direct generalisation of a quantum algorithm, which allows for much greater transparency and control. Transducers naturally characterize general state conversion, rather than only decision problems; provide a very simple treatment of other quantum primitives such as quantum walks; and lend themselves well to time complexity analysis.

arXiv:2311.15873•Quantum•Aug 23, 2024•27 citations

Structure, optimality, and symmetry in shadow unitary inversion

Guocheng Zhen, Yu-Ao Chen, Mingrui Jing +3 more

Reversing unknown quantum dynamics is vital for quantum control and learning, yet full unitary inversion requires a resource-intensive O(d2) queries. Because many applications only require the reversed evolution for a given observable, a critical gap remains in understanding the minimal resources for such targeted reversal. Here, we address this by introducing shadow unitary inversion. We establish a lower bound showing the query complexity must scale at least linearly with system dimension for spectrally biased observables, with the constant determined by the observable’s spectral properties. For qubit case, we construct an explicit, deterministic three-query sequential protocol achieving exact shadow inversion and completely characterize all admissible channels, with numerical evidence suggesting optimality. For higher dimensions, we develop a semidefinite-programming formulation and introduce a representation-theoretic symmetry reduction that decomposes the optimization into invariant blocks, substantially reducing the problem size. Shadow unitary inversion thus offers a resource-efficient path to inverse-dynamics estimation for future quantum control, diagnostics, and learning tasks. Reversing unitary operations is crucial in quantum computing and control, yet remains a challenging task. The authors introduce shadow unitary inversion, achieving efficient inversion at the expectation value level with reduced query complexity, offering a promising approach for quantum error correction and information recovery.

arXiv:2510.24880•Communications Physics•May 20, 2026•2 citations

New quantum algorithms and quantum lower bounds

Andrew Chi-Chih Yao, Shengyu Zhang

The last decade witnessed a great surge of fruitful studies in the new paradigm of quantum computing. Remarkable progress has been made in all the areas including quantum algorithms, quantum complexity theory, quantum error-correcting code, quantum information theory, quantum cryptography and physical implementations of quantum computers. However, quantum algorithm design, probably the most important task in quantum computing, did not make as much progress as people expected. This thesis aims at both designing new quantum algorithms and studying why efficient quantum algorithms are so hard to design by proving many lower bounds on quantum query complexity for various problems. We first review (and generalize) known techniques for designing quantum algorithms and for proving quantum lower bounds. Using these techniques, we then study the quantum query complexity for many problems, including some specific problems such as Graph Matching and other natural graph properties, the general tuple search, and local search. We also study the lowest possible quantum query complexity for a class of functions as a whole, such as graph properties, circular functions, and functions invariant of a transitive permutation group, where tight results are given in all these cases. Finally for the quantum lower bounds techniques themselves, we study the main two techniques and show that they are incomparable in power. For the most widely used one, which has a lot of parameters to choose, we show limitations for it in terms of certificate complexity. This implies that we cannot use the method to prove better lower bounds for almost all known open problems in this area.

•Jan 1, 2006•3 citations

Transducer-based linear combination of unitaries: theory and applications

Dong An, Dekuan Dong, Changpeng Shao +2 more

Linear combination of unitaries (LCU) is a fundamental primitive in quantum algorithms, whose cost is typically governed by the most expensive unitary appearing in the combination. We develop a transducer-based LCU framework that reduces this worst-case dependence to a weighted average query complexity, when the constituent unitaries share access to a common set of primitive oracles. Consider $A=\sum_j c_j U_j$, where $c_j>0$ and each unitary $U_j$ can be implemented using $C_j$ primitive queries. Given an upper bound $a\geq \|A\|$, our algorithm implements a block-encoding of $A/α$ with rescaling factor $α=\mathcal{O}(a)$, using $\widetilde{\mathcal{O}} (C_{\max}+\overline{C} λ/{a} )$ primitive queries, where $λ=\sum_j c_j$, $C_{\max}=\max_j C_j$, and $\overline{C}= {\sum_j c_j C_j}/λ$. By comparison, the standard LCU construction requires $\widetilde{\mathcal{O}} (C_{\max} λ/{a} )$ primitive queries. The improvement can therefore be substantial when costly unitaries have small weights and $λ/a$ is large. As applications, we obtain improved block-encodings of sparse matrices, leading to quantum algorithms for sparse Hamiltonian simulation and quantum linear systems with near-optimal query complexity up to polylogarithmic factors in all relevant parameters. Our main technique is the transducer framework developed by Belovs, Jeffery, and Yolcu [Quantum, 8:1444 (2024)]. Here we develop a complementary operator-level theory tailored to block-encodings. We identify the resolvent norm $K$ as a key complexity measure for transducer implementation besides the existing catalyst complexity. We show that the transducer action can be converted into an $ε$-approximate block-encoding using only $\mathcal{O}\left(K \log(1/ε)\right)$ queries to the transducer, improving the precision dependence from polynomial to logarithmic.

quant-pharXiv:2609.40073•Oct 1, 2026•0 citations

Minimization of a quantum automaton: The transducer

Ana María Guerra Martins

A model of a quantum automaton (QA), a transducer, working with $n$ qubits is proposed. The quantum states of the automaton are represented by density operators. The linearity of the QA and of the partial trace operator, jointly with the properties of invariant subspaces and of the quotient spaces, are used to minimize the dimension and the cardinality of the state set of the QA.Two main results are obtained in this paper: (a) The conditions that the unitary evolution operators, representing the quantum gates of the QA, must obey in order to reduce its dimension and its state set. (b) An algorithm is developed to find the minimal QA and its complexity is computed. We show that the necessary and sufficient conditions for minimization depend uniquely in the structure of the unitary evolution operators, and they are independent of the initial quantum state of the QA.

arXiv:0807.0193•Physical Review A•Dec 16, 2008•0 citations

A Tight Lower Bound For Non-Coherent Index Erasure

Nathan Lindzey, Ansis Rosmanis

The index erasure problem is a quantum state generation problem that asks a quantum computer to prepare a uniform superposition over the image of an injective function given by an oracle. We prove a tight Ω(√n) lower bound on the quantum query complexity of the non-coherent case of the problem, where, in addition to preparing the required superposition, the algorithm is allowed to leave the ancillary memory in an arbitrary function-dependent state. This resolves an open question of Ambainis, Magnin, Roetteler, and Roland (CCC 2011), who gave a tight bound for the coherent case, the case where the ancillary memory must return to its initial state. To prove our main result, we first extend the so-called automorphism principle (Høyer et al. STOC 2007) to the general adversary method for state conversion problems (Lee et al. STOC 2011), which allows one to exploit the symmetries of these problems to lower bound their quantum query complexity. Using this method, we establish a strong connection between the quantum query complexity of non-coherent symmetric state generation problems and the well-known Krein parameters of association schemes. Krein parameters are usually hard to determine, nevertheless, we give a novel way of computing certain Krein parameters of a commutative association scheme defined over partial permutations. We believe the study of this association scheme may also be of independent interest.

Leibniz international proceedings in informatics•Jan 1, 2020•8 citations
Transducers (Belovs, Jeffery and Yolcu, 2024) are a quantum computing framework describing a quantum algorithm as a unitary converting an input state into a target state using a catalyst, an auxiliary vector that is left unchanged. They are a powerful tool in quantum algorithm design, especially in the context of quantum query complexity: feasible points of the (dual) adversary semidefinite program directly translate into transducers and the optimal transduction complexity is equal to the adversary bound, i.e. the Las Vegas complexity, which is known to characterize bounded-error quantum query complexity. Moreover, contrary to bounded-error algorithms, transducers compose exactly, which limits overheads due to controlling errors in algorithms constructed by composition. Constructing efficient, let alone optimal, transducers in terms of quantum query complexity nevertheless remains a hard task since it still requires solving the adversary SDP and constructing the unitary to obtain an explicit algorithm. In this paper, we show how using the symmetry group of state-conversion problems simplifies both steps. First, using a symmetrization argument, we prove an optimal catalyst can always be chosen covariant under a representation of the symmetry group. Second, we prove that the transducer intertwines two different representations of the group and can thus be chosen block diagonal in the isotypic decomposition of the Hilbert space. Using those methods, we then derive optimal transducers, with optimal constants, for different widely used quantum algorithmic primitives, such as unstructured search, amplitude amplification and amplitude estimation. Our approach extends previous work on the use of representation theory to compute adversary lower bounds (Høyer, Lee, and {\v S}palek, 2007; Ambainis, Magnin, Roetteler and Roland, 2011) to the systematic construction of optimal algorithms.
The paper studies how symmetries can simplify the construction of query-optimal quantum transducers: unitaries that convert input states to target states while returning an auxiliary catalyst unchanged. The objective is the worst-case squared catalyst norm, equal to the state-conversion adversary bound, rather than the number of queries in a fixed-length bounded-error algorithm.
For state-conversion problems with finite or compact Lie symmetry groups, it develops a symmetrization procedure that produces weakly covariant catalysts without increasing cost. Stabilizer invariance then restricts the catalyst space. The input-independent transducer is shown to intertwine the input-side and output-side representations on the relevant state spans, enabling an isotypic block decomposition. Strong covariance, which fixes a trivial workspace representation, is not generally sufficient: examples show both infeasibility and suboptimality.
Applications give exact optimal transduction costs W=(N−M)/(4M)W=\sqrt{(N-M)/(4M)}W=(N−M)/(4M)​ for preparing a uniform superposition over marked items when their number is either MMM or at least MMM, and W=1−ε2/(2ε)W=\sqrt{1-\varepsilon^2}/(2\varepsilon)W=1−ε2​/(2ε) for amplitude amplification with overlap either ε\varepsilonε or at least ε\varepsilonε. Covariance reduces catalyst optimization to small problems; matching lower bounds establish optimality. For translation-invariant, periodic amplitude-estimation state conversion, the cost is ∑n∈2Z+1∣h^n∣\sum_{n\in2\mathbb Z+1}|\hat h_n|∑n∈2Z+1​∣h^n​∣, where h(ω)=(1−g(ω))/(2sin⁡ω)h(\omega)=(1-g(\omega))/(2\sin\omega)h(ω)=(1−g(ω))/(2sinω) and ggg is the target overlap kernel.
The analysis concerns query cost, not implementation time or space. Some constructions require infinite-dimensional workspaces; finite-dimensional realization or truncation, including its error–space trade-offs, remains open.
Quantum query complexity has several nice properties with respect to composition. First, bounded-error quantum query algorithms can be composed without incurring log factors through error reduction e x a c t n e s s . Second, through careful accounting t h r i f t i n e s s , the total query complexity is smaller if subroutines are mostly run on cheaper inputs -- a property that is much less obvious in quantum algorithms than in their classical counterparts. While these properties were previously seen through the model of span programs (alternatively, the dual adversary bound), a recent work by two of the authors (Belovs, Yolcu 2023) showed how to achieve these benefits without converting to span programs, by defining quantum Las Vegas query complexity . Independently, recent works, including by one of the authors (Jeffery 2022), have worked towards bringing thriftiness to the more practically significant setting of quantum t i m e complexity.In this work, we show how to achieve both exactness and thriftiness in the setting of time complexity. We generalize the quantum subroutine composition results of Jeffery 2022 so that, in particular, no error reduction is needed. We give a time complexity version of the well-known result in quantum query complexity, Q ( f ∘ g ) = O ( Q ( f ) ⋅ Q ( g ) ) , without log factors.We achieve this by employing a novel approach to the design of quantum algorithms based on what we call t r a n s d u c e r s , and which we think is of large independent interest. While a span program is a completely different computational model, a transducer is a direct generalisation of a quantum algorithm, which allows for much greater transparency and control. Transducers naturally characterize general state conversion, rather than only decision problems; provide a very simple treatment of other quantum primitives such as quantum walks; and lend themselves well to time complexity analysis.
Reversing unknown quantum dynamics is vital for quantum control and learning, yet full unitary inversion requires a resource-intensive O(d2) queries. Because many applications only require the reversed evolution for a given observable, a critical gap remains in understanding the minimal resources for such targeted reversal. Here, we address this by introducing shadow unitary inversion. We establish a lower bound showing the query complexity must scale at least linearly with system dimension for spectrally biased observables, with the constant determined by the observable’s spectral properties. For qubit case, we construct an explicit, deterministic three-query sequential protocol achieving exact shadow inversion and completely characterize all admissible channels, with numerical evidence suggesting optimality. For higher dimensions, we develop a semidefinite-programming formulation and introduce a representation-theoretic symmetry reduction that decomposes the optimization into invariant blocks, substantially reducing the problem size. Shadow unitary inversion thus offers a resource-efficient path to inverse-dynamics estimation for future quantum control, diagnostics, and learning tasks. Reversing unitary operations is crucial in quantum computing and control, yet remains a challenging task. The authors introduce shadow unitary inversion, achieving efficient inversion at the expectation value level with reduced query complexity, offering a promising approach for quantum error correction and information recovery.
The last decade witnessed a great surge of fruitful studies in the new paradigm of quantum computing. Remarkable progress has been made in all the areas including quantum algorithms, quantum complexity theory, quantum error-correcting code, quantum information theory, quantum cryptography and physical implementations of quantum computers. However, quantum algorithm design, probably the most important task in quantum computing, did not make as much progress as people expected. This thesis aims at both designing new quantum algorithms and studying why efficient quantum algorithms are so hard to design by proving many lower bounds on quantum query complexity for various problems. We first review (and generalize) known techniques for designing quantum algorithms and for proving quantum lower bounds. Using these techniques, we then study the quantum query complexity for many problems, including some specific problems such as Graph Matching and other natural graph properties, the general tuple search, and local search. We also study the lowest possible quantum query complexity for a class of functions as a whole, such as graph properties, circular functions, and functions invariant of a transitive permutation group, where tight results are given in all these cases. Finally for the quantum lower bounds techniques themselves, we study the main two techniques and show that they are incomparable in power. For the most widely used one, which has a lot of parameters to choose, we show limitations for it in terms of certificate complexity. This implies that we cannot use the method to prove better lower bounds for almost all known open problems in this area.
Linear combination of unitaries (LCU) is a fundamental primitive in quantum algorithms, whose cost is typically governed by the most expensive unitary appearing in the combination. We develop a transducer-based LCU framework that reduces this worst-case dependence to a weighted average query complexity, when the constituent unitaries share access to a common set of primitive oracles. Consider A=∑jcjUjA=\sum_j c_j U_jA=∑j​cj​Uj​, where cj>0c_j>0cj​>0 and each unitary UjU_jUj​ can be implemented using CjC_jCj​ primitive queries. Given an upper bound a≥∥A∥a\geq \|A\|a≥∥A∥, our algorithm implements a block-encoding of A/αA/αA/α with rescaling factor α=O(a)α=\mathcal{O}(a)α=O(a), using O~(Cmax⁡+C‾λ/a)\widetilde{\mathcal{O}} (C_{\max}+\overline{C} λ/{a} )O(Cmax​+Cλ/a) primitive queries, where λ=∑jcjλ=\sum_j c_jλ=∑j​cj​, Cmax⁡=max⁡jCjC_{\max}=\max_j C_jCmax​=maxj​Cj​, and C‾=∑jcjCj/λ\overline{C}= {\sum_j c_j C_j}/λC=∑j​cj​Cj​/λ. By comparison, the standard LCU construction requires O~(Cmax⁡λ/a)\widetilde{\mathcal{O}} (C_{\max} λ/{a} )O(Cmax​λ/a) primitive queries. The improvement can therefore be substantial when costly unitaries have small weights and λ/aλ/aλ/a is large. As applications, we obtain improved block-encodings of sparse matrices, leading to quantum algorithms for sparse Hamiltonian simulation and quantum linear systems with near-optimal query complexity up to polylogarithmic factors in all relevant parameters. Our main technique is the transducer framework developed by Belovs, Jeffery, and Yolcu [Quantum, 8:1444 (2024)]. Here we develop a complementary operator-level theory tailored to block-encodings. We identify the resolvent norm KKK as a key complexity measure for transducer implementation besides the existing catalyst complexity. We show that the transducer action can be converted into an εεε-approximate block-encoding using only O(Klog⁡(1/ε))\mathcal{O}\left(K \log(1/ε)\right)O(Klog(1/ε)) queries to the transducer, improving the precision dependence from polynomial to logarithmic.
A model of a quantum automaton (QA), a transducer, working with nnn qubits is proposed. The quantum states of the automaton are represented by density operators. The linearity of the QA and of the partial trace operator, jointly with the properties of invariant subspaces and of the quotient spaces, are used to minimize the dimension and the cardinality of the state set of the QA.Two main results are obtained in this paper: (a) The conditions that the unitary evolution operators, representing the quantum gates of the QA, must obey in order to reduce its dimension and its state set. (b) An algorithm is developed to find the minimal QA and its complexity is computed. We show that the necessary and sufficient conditions for minimization depend uniquely in the structure of the unitary evolution operators, and they are independent of the initial quantum state of the QA.
The index erasure problem is a quantum state generation problem that asks a quantum computer to prepare a uniform superposition over the image of an injective function given by an oracle. We prove a tight Ω(√n) lower bound on the quantum query complexity of the non-coherent case of the problem, where, in addition to preparing the required superposition, the algorithm is allowed to leave the ancillary memory in an arbitrary function-dependent state. This resolves an open question of Ambainis, Magnin, Roetteler, and Roland (CCC 2011), who gave a tight bound for the coherent case, the case where the ancillary memory must return to its initial state. To prove our main result, we first extend the so-called automorphism principle (Høyer et al. STOC 2007) to the general adversary method for state conversion problems (Lee et al. STOC 2011), which allows one to exploit the symmetries of these problems to lower bound their quantum query complexity. Using this method, we establish a strong connection between the quantum query complexity of non-coherent symmetric state generation problems and the well-known Krein parameters of association schemes. Krein parameters are usually hard to determine, nevertheless, we give a novel way of computing certain Krein parameters of a commutative association scheme defined over partial permutations. We believe the study of this association scheme may also be of independent interest.