Quantum and classical query complexities for generalized Deutsch-Jozsa problems

DOI10.1007/S11128-020-02652-2MaRDI QIDQ2677211zbMATH OpenOpenAlexFDO

Authors Zhengwei Xie, Daowen Qiu

Publication date 13 January 2023

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

Full work available at URL https://doi.org/10.1007/s11128-020-02652-2

zbMATH Keywords

correlation testinggeneralized Deutsch-Jozsa problemquantum amplitude amplificationquery complexity

Mathematics Subject Classification ID

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

Recommendations

• Revisiting Deutsch-Jozsa algorithm
• A different Deutsch-Jozsa
• The Deutsch-Jozsa problem: de-quantisation and entanglement
• Testing Boolean functions properties
• On a poset of quantum exact promise problems

Cites work

• An o(n) monotonicity tester for Boolean functions over the hypercube
• Asymptotic behavior of perturbations of symmetric functions
• Complexity measures and decision tree complexity: a survey.
• DE-QUANTIZING THE SOLUTION OF DEUTSCH'S PROBLEM
• Generalization and demonstration of an entanglement-based Deutsch-jozsa-like algorithm using a 5-qubit quantum computer
• Generalized Walsh transforms of symmetric and rotation symmetric Boolean functions are linear recurrent
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• Linear recurrences and asymptotic behavior of exponential sums of symmetric Boolean functions
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• On the correlation of symmetric functions
• Optimal separation in exact query complexities for Simon's problem
• Property testing and its connection to learning and approximation
• Quantum algorithms for learning Walsh spectra of multi-output Boolean functions
• Quantum and classical query complexities for generalized Simon's problem
• Quantum Property Testing
• Rapid solution of problems by quantum computation
• Schwankung von Polynomen zwischen Gitterpunkten. (Oscillations of polynomials between lattice points)
• Settling the query complexity of non-adaptive junta testing
• The quantum query complexity of approximating the median and related statistics

Cited in

(16)

• The Deutsch-Jozsa problem: de-quantisation and entanglement
• Sharp quantum versus classical query complexity separations
• A different Deutsch-Jozsa
• On a poset of quantum exact promise problems
• Forrelation: a problem that optimally separates quantum from classical computing
• Generalizations of the distributed Deutsch-Jozsa promise problem
• An observer-based de-quantisation of Deutsch's algorithm
• Entanglement tensor for a general pure multipartite quantum state
• On the uselessness of quantum queries
• scientific article; zbMATH DE number 2076191 (Why is no real title available?)
• Forrelation: a problem that optimally separates quantum from classical computing
• Initialization-free generalized Deutsch-Jozsa algorithm
• Testing Boolean functions properties
• Comparing two quantum oracles using the Deutsch-Jozsa algorithm
• DE-QUANTIZING THE SOLUTION OF DEUTSCH'S PROBLEM
• Randomized decision tree complexity of Deutsch-Jozsa problem and a generalization

This page was built for publication: Quantum and classical query complexities for generalized Deutsch-Jozsa problems

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