From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm
From MaRDI portal
Publication:2684233
DOI10.1007/s11128-020-02975-0OpenAlexW3118599195MaRDI QIDQ2684233
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
quantum computationBoolean functionsum-of-squares representationalgorithm frameworkquantum query algorithm
Quantum computation (81P68) Boolean functions (06E30) Quantum algorithms and complexity in the theory of computing (68Q12)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Virtual boundaries of Hadamard spaces with admissible actions of higher rank
- The homology of certain subgroups of the symmetric group with coefficients in \(\text{Lie}(n)\)
- On the degree of Boolean functions as real polynomials
- Quantum query as a state decomposition
- Complexity measures and decision tree complexity: a survey.
- Generalization and demonstration of an entanglement-based Deutsch-jozsa-like algorithm using a 5-qubit quantum computer
- Revisiting Deutsch-Jozsa algorithm
- On exact quantum query complexity
- Exact Quantum Query Complexity of EXACT and THRESHOLD
- Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$
- Query Complexity in Expectation
- Rapid solution of problems by quantum computation
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Nondeterministic Quantum Query and Communication Complexities
- Quantum Query Algorithms are Completely Bounded Forms.
- UNDERSTANDING QUANTUM ALGORITHMS VIA QUERY COMPLEXITY
- On the sum-of-squares degree of symmetric quadratic functions
- Polynomials, quantum query complexity, and Grothendieck's inequality
- Quantum lower bounds by polynomials
- A Sum of Squares Approximation of Nonnegative Polynomials
- Quantum lower bounds by quantum arguments
This page was built for publication: From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm
