Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Journal of Mathemati...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Journal of Mathematical Physics
Article . 2023 . Peer-reviewed
License: CC BY
Data sources: Crossref
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2023
Data sources: zbMATH Open
https://dx.doi.org/10.48550/ar...
Article . 2023
License: CC BY
Data sources: Datacite
versions View all 4 versions
addClaim

Semantic embedding for quantum algorithms

Authors: Zane M. Rossi; Isaac L. Chuang;

Semantic embedding for quantum algorithms

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ätze, 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.

Country
United States
Keywords

Quantum Physics, Quantum computation, Semantics in the theory of computing, FOS: Physical sciences, Quantum algorithms and complexity in the theory of computing, Quantum Physics (quant-ph), 004, 620

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    4
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Top 10%
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
4
Top 10%
Average
Top 10%
Green
hybrid