From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm

DOI10.1007/S11128-020-02975-0MaRDI QIDQ2684233zbMATH OpenOpenAlexFDO

Authors Guo-Liang Xu, Daowen Qiu

Publication date 16 February 2023

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11128-020-02975-0

zbMATH Keywords

algorithm frameworkBoolean functionquantum computationquantum query algorithmsum-of-squares representation

Mathematics Subject Classification ID

Boolean functions (06E30) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Recommendations

• SOFSEM 2005: Theory and Practice of Computer Science
• On exact quantum query complexity
• Boolean functions identification via quantum computing methods
• A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function
• Quantum lower bounds by polynomials

Cites work

• A Sum of Squares Approximation of Nonnegative Polynomials
• Complexity measures and decision tree complexity: a survey.
• Exact quantum query complexity of \(\mathrm{EXACT}_{k,l}^n\)
• Exact quantum query complexity of EXACT and THRESHOLD
• Generalization and demonstration of an entanglement-based Deutsch-jozsa-like algorithm using a 5-qubit quantum computer
• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 5605071 (Why is no real title available?)
• scientific article; zbMATH DE number 3829252 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• Nondeterministic Quantum Query and Communication Complexities
• On exact quantum query complexity
• On the degree of Boolean functions as real polynomials
• On the sum-of-squares degree of symmetric quadratic functions
• Polynomials, quantum query complexity, and Grothendieck's inequality
• Quantum lower bounds by polynomials
• Quantum lower bounds by quantum arguments
• Quantum query algorithms are completely bounded forms
• Quantum query as a state decomposition
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Query complexity in expectation
• Rapid solution of problems by quantum computation
• Revisiting Deutsch-Jozsa algorithm
• The homology of certain subgroups of the symmetric group with coefficients in \(\text{Lie}(n)\)
• Understanding quantum algorithms via query complexity
• Virtual boundaries of Hadamard spaces with admissible actions of higher rank

Cited in

(2)

• scientific article; zbMATH DE number 2051219 (Why is no real title available?)
• Sensitivity of symmetric Boolean functions

Describes a project that uses

Uses Software

• Sostools

This page was built for publication: From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2684233)