An adversary bound for quantum signal processing

• URL: http://arxiv.org/abs/2506.20484v1
• Date: Wed, 25 Jun 2025 14:31:34 GMT
• Title: An adversary bound for quantum signal processing
• Authors: Lorenzo Laneve,
• Abstract summary: We study the class of transformations achievable by M-QSP.<n>We show that a M-QSP protocol of minimal space is thus reduced to a rank minimization problem involving the feasible solution space of the adversary bound.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum signal processing (QSP) and quantum singular value transformation (QSVT), have emerged as unifying frameworks in the context of quantum algorithm design. These techniques allow to carry out efficient polynomial transformations of matrices block-encoded in unitaries, involving a single ancilla qubit. Recent efforts try to extend QSP to the multivariate setting (M-QSP), where multiple matrices are transformed simultaneously. However, this generalization faces problems not encountered in the univariate counterpart: in particular, the class of polynomials achievable by M-QSP seems hard to characterize. In this work we borrow tools from query complexity, namely the state conversion problem and the adversary bound: we first recast QSP as a state conversion problem over the Hilbert space of square-integrable functions. We then show that the adversary bound for a $|0\rangle \mapsto (P, Q)$ state conversion in this space precisely identifies all and only the QSP protocols over $SU(2)$ in the univariate case. Motivated by this result, we extend the formalism to M-QSP: the computation of a M-QSP protocol of minimal space is thus reduced to a rank minimization problem involving the feasible solution space of the adversary bound.

Related papers

• Double-bracket algorithm for quantum signal processing without post-selection [0.0]
  Quantum signal processing (QSP) is a fundamental primitive in various quantum algorithms.<n>Despite its versatility, a potentially underappreciated challenge is that all systematic protocols for implementing QSP rely on post-selection.<n>We introduce a new formula for implementing QSP transformations of Hermitian matrices, which requires neither auxiliary qubits nor post-selection.
  arXiv  Detail & Related papers  (2025-04-01T18:00:04Z)
• Polynomial time constructive decision algorithm for multivariable quantum signal processing [0.7332146059733189]
  Multivariable quantum signal processing (M-QSP) is proposed. M-QSP interleaves signal operators corresponding to each variable with signal processing operators. A classical algorithm is proposed to determine whether a given pair of Laurents can be implemented by M-QSP.
  arXiv  Detail & Related papers  (2024-10-03T09:30:35Z)
• Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
  Quantum signal processing (QSP) provides a systematic framework for implementing a transformation of a linear operator.<n>Recent works have developed randomized compiling, a technique that promotes a unitary gate to a quantum channel.<n>Our algorithm implements a probabilistic mixture of randomizeds, strategically chosen so that the average evolution converges to that of a target function, with an error quadratically smaller than that of an equivalent individual.
  arXiv  Detail & Related papers  (2024-09-05T17:56:51Z)
• Geometric Quantum Machine Learning with Horizontal Quantum Gates [41.912613724593875]
  We propose an alternative paradigm for the symmetry-informed construction of variational quantum circuits. We achieve this by introducing horizontal quantum gates, which only transform the state with respect to the directions to those of the symmetry. For a particular subclass of horizontal gates based on symmetric spaces, we can obtain efficient circuit decompositions for our gates through the KAK theorem.
  arXiv  Detail & Related papers  (2024-06-06T18:04:39Z)
• On variants of multivariate quantum signal processing and their characterizations [0.0]
  Quantum signal processing (QSP) is a highly successful algorithmic primitive in quantum computing. We show that Haah's characterization of general QSP can be extended to homogeneous bivariable (commuting) quantum signal processing. We also show a similar result for an alternative inhomogeneous variant when the degree in one of the variables is at most 1, but construct a counterexample where both variables have degree 2.
  arXiv  Detail & Related papers  (2023-12-14T16:06:58Z)
• Unitary Complexity and the Uhlmann Transformation Problem [41.67228730328207]
  We introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes. We use this framework to study the complexity of transforming one entangled state into another via local operations. Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.
  arXiv  Detail & Related papers  (2023-06-22T17:46:39Z)
• Quantum process tomography of continuous-variable gates using coherent states [49.299443295581064]
  We demonstrate the use of coherent-state quantum process tomography (csQPT) for a bosonic-mode superconducting circuit. We show results for this method by characterizing a logical quantum gate constructed using displacement and SNAP operations on an encoded qubit.
  arXiv  Detail & Related papers  (2023-03-02T18:08:08Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
  arXiv  Detail & Related papers  (2023-01-05T11:05:22Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle [0.0]
  Recent work shows that quantum signal processing (QSP) and its multi-qubit lifted version, quantum singular value transformation (QSVT) QSVT transforms and improve the presentation of most quantum algorithms.
  arXiv  Detail & Related papers  (2022-05-12T17:58:59Z)
• General Hamiltonian Representation of ML Detection Relying on the Quantum Approximate Optimization Algorithm [74.6114458993128]
  The quantum approximate optimization algorithm (QAOA) conceived for solving optimization problems can be run on the existing noisy intermediate-scale quantum (NISQ) devices. We solve the maximum likelihood (ML) detection problem for general constellations by appropriately adapting the QAOA. In particular, for an M-ary Gray-mapped quadrature amplitude modulation (MQAM) constellation, we show that the specific qubits encoding the in-phase components and those encoding the quadrature components are independent in the quantum system of interest.
  arXiv  Detail & Related papers  (2022-04-11T14:11:24Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.