CS Paper Radar

Optimal transducers using symmetries

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

cs.CC quant-ph ·submitted 2026-10-01 17:43 UTC · v1
theoryhot direction

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.

Comment
39 pages, 6 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Strong Selective and List-Decoding Direct Product Theorems for Quantum Query Complexity

cs.CC quant-ph ·2026-09-22 ·Paul Beame, Niels Kornerup, Michael Whitmeyer
theory similarity 0.71
Abstract · 64 pages, 3 figures, submitted to QIP 2027

Quantum strong direct-product theorems for specific functions have been known for nearly two decades. These have been extended to general results for function computation and state generation. The proofs of these results use a version of the multiplicative adversary method that does not naturally extend to relations. Standard strong direct-product theorems apply when algorithms must correctly answer every given question. Prior work extended them to equivalent threshold direct-product theorems, which require answers to all questions but only require that most answers are correct. We focus on two further generalizations. Strong selective direct-products apply to algorithms that adaptively choose, based on what they learn from queries, which questions from a large list to answer. This generalization is relational and useful for proving time-space tradeoffs. We prove a quantum strong selective direct-product theorem for all functions using a relational formulation of the multiplicative adversary method by Jeffery and Zur which we prove, via an equivalent formulation, satisfies a strong selective direct product property and captures any query lower bound for functions proven by negative-weights adversaries. The second generalization is list-decoding direct product problems introduced by Ben-David and Blais for classical query complexity. These allow an algorithm to produce a large list of possible output vectors such that one of them is fully correct. They proved that such theorems hold for randomized complexity of all Boolean functions. We prove a quantum analogue of this theorem for all partial Boolean-valued functions. We show that strong list-decoding direct-product theorems are implied by a special case of multiplicative adversaries which we show, via a new reduction, can be obtained from negative-weights adversaries for any Boolean-valued function.

0.26

Quantum lower bounds for convex optimization and real matrix-vector query problems

cs.DS quant-phmath.OC ·2026-09-04 ·Andrew M. Childs
theory similarity 0.69
Abstract · 29 pages. v2: additional discussion of technical approach in introduction, minor corrections

We (the author and the AI systems that did the heavy lifting) show that the quantum query complexity of minimizing a convex function over a convex subset of $\mathbb{R}^n$ with evaluation and membership queries is $\tildeΩ(n)$, nearly matching the best known upper bound. In particular, we show this even for quadratic minimization, which is equivalent to inverting an $n \times n$ real matrix using matrix-vector queries. We also show linear or nearly linear lower bounds on the quantum query complexity of computing the trace, the sign of the determinant, and the magnitude of the determinant of a real matrix in the matrix-vector query model. We use a novel quantum lower bound technique, the determinantal witness method, based on identifying a witness whose Fourier transform vanishes on low-rank matrices and that correlates well with the function being computed.

0.29

A Grover-Amplified Oracle for Maximum Clique on Graph, Minimum Hitting set and Dualizations on Hypergraphs Built on Quantum Phase Estimation

cs.CC quant-ph ·2026-11-07 ·Francisco Piñero, Fernando L. \Pelayo, Hernan I. de la Cruz, Jose J. Paulet, Mauro Mezzini +1 more
similarity 0.69
Abstract

In this paper, we use a quantum circuit called the Graph Encoding Operator which, applied to the complement $\bar G$ of any graph $G$, yields an oracle for the maximum clique problem suitable for amplification via Grover's algorithm. Analogously, we devise a Hypergraph Encoding Operator which, when applied to a hypergraph $\mathcal H$, yields an oracle for the minimum hitting set suitable for amplification via Grover's algorithm. Interestingly, the latter oracle provides, when measured, an approximation of the number of hitting sets of the hypergraph, thus solving the dualization problem for positive Boolean functions represented in a positive irredundant disjunctive normal form. We give the full construction of both operators, prove their correctness, analyze their complexity, and provide an implementation on a quantum simulator. We discuss the resulting complexity, contrast them with existing quantum computer algorithms based on Grover search and we will show that our algorithms outperform, to the best of our knowledge, all of the previous algorithms on space computational complexity by requiring only $O(N)$ number of qubits with respect to the number of vertices $N$, for representing both graphs and hypergraphs in the encoding operator and, consequently, results in an oracle for both graphs and hypergraphs that uses only $O(N)$ qubits even when the hypergraph contains an exponential (on the number of vertices) number of hyperedges.

0.29

A Catalytic Algorithm for Transposing Unknown Qutrit Unitaries with Tight Query Bounds

cs.CC quant-phcs.DS ·2026-10-08 ·Yu-Ao Chen
theory similarity 0.69
Abstract · 31 pages, including supplementary material

We construct exact deterministic circuits for transposing and inverting an unknown qutrit unitary $U\in\mathrm{SU}(3)$ using only forward queries. Three queries prepare a catalyst independently of the input state. Four further queries implement transposition while returning the catalyst unchanged and uncorrelated with the output. Two uses within an antisymmetric encoding implement inversion with eight processing queries and return the same catalyst. Reusing the catalyst implements $m$ transpositions or inversions with $3+4m$ or $3+8m$ total queries, respectively. More generally, we prove that exact transposition and inversion of an unknown $U\in\mathrm{SU}(d)$, $d\ge2$, require at least $d+1$ and $d^2-1$ processing queries, respectively, in fixed causal order. These processing bounds hold for any program state prepared independently of the input state using finitely many forward queries, even if that state is consumed during processing. Both our catalytic qutrit algorithms attain their respective bounds. Moreover, exact qutrit transposition with four processing queries requires at least three preparation queries, and our construction attains this bound.

0.27

Complexity Barriers to State Preparation in Quantum Approximate Optimization

cs.CC quant-ph ·2026-09-25 ·Stuart Hadfield
theoryhighly cited similarity 0.68
Abstract

For many important optimization problems we are restricted to approximate solutions in practice due to computational complexity. Distinct from the exact optimization setting, approximate optimization admits performance measures beyond whether the optimum is found, with different tradeoffs and complexity. For MaxCut, a near-unity (ordinary) approximation ratio can coexist with near-zero improvement (gain) over a random cut. For the standard encoding, the unconditional classical MaxCut-Gain hardness gap implies that \emph{any uniformly efficient quantum or hybrid procedure recovering a fixed positive fraction of the optimal classical gain on every input, with at least inverse-polynomial success probability, would place} NP \emph{in} BQP. Such a procedure is therefore believed impossible under standard assumptions. We broadly address where our worst-case barriers do or do not apply across the quantum algorithm landscape. We prove that the barrier survives quantum random access optimization (QRAO) compression and applies between the classical and relaxed optimal values. For every input, a product state attains the classical optimum. Thus the barrier to reaching the classical threshold does not arise from a need for entanglement. For $d\in\{2,3\}$ variables per qubit, the known decoder transfers encoded energy gain to decoded mean gain by the exact factor $1/d^2$. Combining this identity with MaxCut-Gain hardness gives an operational preparation barrier for QRAO. We also construct hard $n$-qubit families with relative quantum relaxation excess $Θ(1/n)$, while the maximally mixed state has energy approximation ratio $1-Θ(1/n)$, zero encoded energy gain, and hence zero decoded mean gain. Our results separate the effects of relaxation tightness and energy approximation from operational accessibility, motivating more comprehensive accounting in benchmarking and performance assessment.

0.39

State Synthesis with an NP oracle

cs.CC quant-ph ·2026-11-02 ·Aniruddha Sen
theory similarity 0.68
Abstract · 7 pages

In this note, I describe a quantum algorithm that prepares an arbitrary state $|ψ\rangle$ to inverse exponential precision in polynomial time by making queries to an $\mathsf{NP}$ oracle, assuming one can directly query entries of the state vector corresponding to $|ψ\rangle$. The previous best upper bound on the complexity class required by an oracle for this task was $\mathsf{PP}$. I provide evidence that $\mathsf{NP}$ is the best possible upper bound by showing that any quantum algorithm using a $\mathsf{P}$ oracle, or even a $\mathsf{P/poly}$ oracle, requires exponentially many queries. I also discuss some implications of this result for the $\mathsf{QMA}$ search-to-decision problem and unitary synthesis.

0.24

Computational Work Extraction: The Complexity of Catalysts

cs.CC quant-ph ·2026-09-30 ·Atul Singh Arora, Shantanav Chakraborty, Alexandru Cojocaru, Sreyas Saminathan, Uttam Singh
theoryhot direction similarity 0.67
Abstract · 70 pages, 3 Figures; See https://atulsingharora.github.io/cat for updates

We prove maximal separations: $n$-qubit systems can have $Θ(n)$ ergotropy, while every efficient process extracts negligible work, even for Hamiltonians consisting of single-qubit terms. We establish an unconditional existential separation and give an explicit construction in the random oracle model. Assuming the existence of quantum-secure pseudorandom functions, this separation extends to the plain model. This work uncovers an important connection between ergotropy and the complexity of catalytic computation---computation where auxiliary qubits must be finally restored to their initial state. Relative to a random oracle, we establish relational and decision problems that: (i) can be solved efficiently with $λ$ catalysts; but (ii) cannot be solved by any algorithm with $cλ$ catalysts, for any $c<1$. We show this by proving query lower bounds for quantum-space bounded algorithms. As a consequence, for computational ergotropy, catalysts prove to be surprisingly powerful---there is a family of Hamiltonians and states for which catalysts enable efficient extraction of the full $Θ(n)$ ergotropy, while every efficient non-catalytic process extracts negligible work. Furthermore, catalysts also allow us to introduce and instantiate the notion of pseudoergotropy---analogous to pseudorandomness. On the other hand, we show catalysts do not change (information-theoretic) ergotropy. Finally, our work also sheds light on the classical aspect of the problem. First, most of our constructions rely on classical states and Hamiltonians and therefore imply analogous results for classical ergotropy. Second, we show that certain proof of quantumness protocols can be used to generically separate classical and quantum catalytic ergotropy.

0.38

A provable quantum advantage for approximate optimization via decoded quantum interferometry

cs.CC quant-phcs.DS ·2026-10-01 ·Maximilian J. Kramer, Elies Gil-Fuster, Benjamin D. M. Jones, Jens Eisert, Franz J. Schreiber
similarity 0.67
Abstract · 59 pages, 3 figures

Decoded quantum interferometry (DQI) is a novel paradigm for tackling approximate optimization problems on quantum computers. This framework comes with strong performance guarantees and exploits a well-established duality between optimization and coding theory. A central question, however, is whether DQI can actually provably outperform all polynomial-time classical algorithms. In this work, we establish such an advantage in an oracle setting: we consider an optimization task called folded optimal polynomial intersection (folded OPI), where the acceptance sets are chosen randomly and accessed through membership oracles. We establish a strict gap between the approximation ratio achievable by any polynomial-time classical algorithm and the approximation ratio achieved by the DQI algorithm. Our proof builds on Jordan et al.'s DQI framework for approximate optimization and extends the classical lower-bound method underlying Yamakawa and Zhandry's exact-search oracle separation to approximation. Building on recent developments by Sun and Wootters, Horinaga and Yamakawa, and Jo, we further show that a modified version of the DQI algorithm achieves a strictly higher score guarantee on typical sampled folded OPI instances. As a concrete example, for code rate $0.3$, DQI achieves expected scores of approximately $0.85$. In contrast, exceeding the classical threshold of $0.65$ by any fixed amount with constant probability on sampled instances requires super-polynomially many classical membership queries.

0.45