Quantum algorithm design simplified by exploiting symmetry groups
Optimal transducers using symmetries
Computational Complexity
Summary
Quantum algorithms can be very complicated to design and optimize. The authors show that using mathematical symmetries helps make these algorithms easier to build and run optimally. Their approach breaks down complex problems into simpler parts, allowing them to find the best possible setups for well-known quantum tasks like search and amplitude estimation. This makes it easier to create powerful quantum algorithms with less trial and error.
What this means in practice
- •For quantum algorithm developers: Construct optimal building blocks for quantum algorithms such as search and amplitude estimation more efficiently using symmetry-based methods.
- •For quantum software engineers: Reduce complexity and overhead in composing quantum subroutines by leveraging symmetry to create exact and efficient transducers.
Authors
Benoît Dubus, Julien Ladeuze, Jérémie Roland
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.