Optimal transducers using symmetries

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.

Elfs, transducers and quantum walks
Simon Apers, Jérémie Roland, Yuxin Zhang
arXiv12 Oct 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
Optomechanical transducers for gigahertz frequency ultrasound imaging
Lisa Hackett, Chang Ge, Alex Miera +2
arXiv10 Oct 2026PreprintCC BY 4.0Full textApplied physics & instrumentation Optics & photonicsarXiv
Improved quantum volume estimation with transducers and amortized quantum walks
Arjan Cornelissen, Simon Apers, Sander Gribling
HAL5 Oct 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationHALarXiv
Lens-Aware Differentiable Beamforming for In Vivo Distributed Aberration Correction with Curvilinear Transducers
Benjamin N. Frey, Robin van Velzen, Hoda S. Hashemi +7
arXiv16 Sep 2026PreprintCC BY-NC-SA 4.0Full textBiological & medical physicsarXiv
Reduced-parameter ultrasound electrical impedance spectroscopy for characterization of piezoelectric transducers and polymer materials
Jhoan F Acevedo-Espinosa, Flávio O S D’amato, Marcos V D Vermelho +5
Ultrasonics3 Sep 2026Peer-reviewedCC BY 4.0Full textApplied physics & instrumentationHAL

Cite

BibTeX RIS

BibTeX

@misc{dubus2026optimal,
  title = {{Optimal transducers using symmetries}},
  author = {Benoît Dubus and Julien Ladeuze and Jérémie Roland},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.02133},
  eprint = {2610.02133},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.02133},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Optimal transducers using symmetries
AU  - Benoît Dubus
AU  - Julien Ladeuze
AU  - Jérémie Roland
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2610.02133
UR  - https://arxiv.org/abs/2610.02133
AB  - 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.
ER  -

Abstract

Related

Cite