Quantum Channel Polynomial Processing

• URL: http://arxiv.org/abs/2607.06557v1
• Date: Tue, 07 Jul 2026 17:57:48 GMT
• Title: Quantum Channel Polynomial Processing
• Abstract summary: We introduce a quantum algorithmic framework based on probabilistic mixtures of unitary channels.<n>We show that our framework supports a flexible tradeoff between sample- and query complexity.<n>We argue that our framework can be scaled seamlessly from NISQ to fault-tolerant quantum computing.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a quantum algorithmic framework based on probabilistic mixtures of unitary channels that, similar to the framework of quantum singular value transformations, enables the application of arbitrary polynomials of hermitian operators onto arbitrary initial states. We show that our framework supports a flexible tradeoff between sample- and query complexity ranging from optimal query complexity, meaning logarithmic in the error, and exponentially scaling sample complexity to sub-polynomial query complexity in the error and polynomial sample complexity. Combined with the considerably lower quantum circuit complexity, compared to quantum singular value transformations with a linear combination of unitaries block encoding, we argue that our framework can be seamlessly scaled from NISQ to fault-tolerant quantum computing.

Related papers

• Sample Complexity of Composite Quantum Hypothesis Testing [1.376408511310322]
  We characterize the sample complexity of symmetric composite binary quantum hypothesis testing.<n>Specifically, we derive lower bounds that generalize the sample complexity of simple QHT.<n>We extend our analysis to the differentially private setting, establishing the sample complexity for privacy-preserving composite QHT.
  arXiv  Detail & Related papers  (2026-01-13T14:15:12Z)
• Statistical phase-space complexity of continuous-variable quantum channels [5.3884682123261705]
  In this work, we utilize this complexity quantifier of quantum states to study the complexity of single-mode bosonic quantum channels.<n>We define the complexity of quantum channels as the maximal amount of complexity they can generate from an initial state with the minimal complexity.
  arXiv  Detail & Related papers  (2025-10-14T18:00:04Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Quantum Signal Processing and Quantum Singular Value Transformation on $U(N)$ [8.264300525515097]
  Quantum signal processing and quantum value transformation are powerful tools to implement transformations of block-encoded matrices on quantum computers. We propose a framework which realizes multiples simultaneously from a block-encoded input. We also give an algorithm to construct the quantum circuit that gives the desired transformation.
  arXiv  Detail & Related papers  (2024-07-19T14:15:20Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [88.57261102552016]
  The anticipated applications of quantum computers span across science and industry.<n>We present a survey of several potential application areas of quantum algorithms.<n>We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Unitary Complexity and the Uhlmann Transformation Problem [39.6823854861458]
  We introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes.<n>We use this framework to study the complexity of transforming one entangled state into another via local operations.<n>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)
• Resource-Dependent Complexity of Quantum Channels [5.633571140534384]
  We introduce a new framework for quantifying the complexity of quantum channels.<n>This class of convex functions is designed to analyze the complexity of both open and closed quantum systems.
  arXiv  Detail & Related papers  (2023-03-20T17:44:57Z)
• 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)
• Quantum Parameterized Complexity [1.01129133945787]
  We introduce the quantum analogues of a range of parameterized complexity classes. This framework exposes a rich classification of the complexity of parameterized versions of QMA-hard problems.
  arXiv  Detail & Related papers  (2022-03-15T15:34:38Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs. Coded Systems [69.33243249411113]
  We show that Pauli errors incur the lowest sampling overhead among a large class of realistic quantum channels. We conceive a scheme amalgamating QEM with quantum channel coding, and analyse its sampling overhead reduction compared to pure QEM.
  arXiv  Detail & Related papers  (2020-12-15T15:51:27Z)

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.