Semantic embedding for quantum algorithms
From MaRDI portal
Publication:6142803
Abstract: The study of classical algorithms is supported by an immense understructure, founded in logic, type, and category theory, that allows an algorithmist to reason about the sequential manipulation of data irrespective of a computation's realizing dynamics. As quantum computing matures, a similar need has developed for an assurance of the correctness of high-level quantum algorithmic reasoning. Parallel to this need, many quantum algorithms have been unified and improved using quantum signal processing (QSP) and quantum singular value transformation (QSVT), which characterize the ability, by alternating circuit ans"atze, to transform the singular values of sub-blocks of unitary matrices by polynomial functions. However, while the algebraic manipulation of polynomials is simple (e.g., compositions and products), the QSP/QSVT circuits realizing analogous manipulations of their embedded polynomials are non-obvious. This work constructs and characterizes the runtime and expressivity of QSP/QSVT protocols where circuit manipulation maps naturally to the algebraic manipulation of functional transforms (termed semantic embedding). In this way, QSP/QSVT can be treated and combined modularly, purely in terms of the functional transforms they embed, with key guarantees on the computability and modularity of the realizing circuits. We also identify existing quantum algorithms whose use of semantic embedding is implicit, spanning from distributed search to proofs of soundness in quantum cryptography. The methods used, based in category theory, establish a theory of semantically embeddable quantum algorithms, and provide a new role for QSP/QSVT in reducing sophisticated algorithmic problems to simpler algebraic ones.
Recommendations
- Topological structure of quantum algorithms
- Geometry of abstraction in quantum computation
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Configurable sublinear circuits for quantum state preparation
- A LOGIC FOR QUANTUM COMPUTATION AND CLASSICAL SIMULATION OF QUANTUM ALGORITHMS
Cites work
- scientific article; zbMATH DE number 555217 (Why is no real title available?)
- scientific article; zbMATH DE number 6131346 (Why is no real title available?)
- scientific article; zbMATH DE number 3302923 (Why is no real title available?)
- scientific article; zbMATH DE number 3367095 (Why is no real title available?)
- A category-theoretic account of program modules
- An axiomatic basis for computer programming
- Computationally binding quantum commitments
- Entanglement is not necessary for perfect discrimination between unitary operations
- Fixed-point quantum search
- On lattices, learning with errors, random linear codes, and cryptography
- Quantum Arthur-Merlin games
- Quantum programming languages: survey and bibliography
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
- Schrödinger's pirate: how to trace a quantum decoder
- Towards a quantum programming language
- Verification of sequential and concurrent programs
Cited in
(4)- Quantum plug n' play: modular computation in the quantum regime
- scientific article; zbMATH DE number 5667324 (Why is no real title available?)
- Robust iterative method for symmetric quantum signal processing in all parameter regimes
- Quantum aspects of semantic analysis and symbolic artificial intelligence
This page was built for publication: Semantic embedding for quantum algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6142803)
