Semantic embedding for quantum algorithms

DOI10.1063/5.0160910arXiv2304.14392OpenAlexW4390245860MaRDI QIDQ6142803FDOQ6142803

Authors: Isaac L. Chuang 

Publication date: 4 January 2024

Published in: Journal of Mathematical Physics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2304.14392

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

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Semantics in the theory of computing (68Q55)

Cites Work

• Entanglement is not necessary for perfect discrimination between unitary operations
• Title not available (Why is that?)
• Towards a quantum programming language
• Quantum programming languages: survey and bibliography
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum Arthur-Merlin games
• An axiomatic basis for computer programming
• On lattices, learning with errors, random linear codes, and cryptography
• Title not available (Why is that?)
• Fixed-point quantum search
• Verification of sequential and concurrent programs
• A category-theoretic account of program modules
• Computationally binding quantum commitments
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Schrödinger's pirate: how to trace a quantum decoder
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning

Cited In (4)

• Quantum plug n' play: modular computation in the quantum regime
• Title not available (Why is that?)
• 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)