Quantum Algorithms for Classical Probability Distributions

DOI10.4230/LIPIcs.ESA.2019.16OpenAlexW2978804772MaRDI QIDQ5075751

Aleksandrs Belovs

Publication date: 11 May 2022

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

zbMATH Keywords

Hellinger distancequantum query complexityquantum adversary methoddistinguishing probability distributions

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quantum algorithms for learning symmetric juntas via the adversary bound
• Improved bounds on quantum learning algorithms
• New Results on Quantum Property Testing
• Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection
• Positive Definite Matrices
• Quantum lower bounds for the collision and the element distinctness problems
• Learning DNF over the Uniform Distribution Using a Quantum Example Oracle
• Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
• Quantum Query Complexity of Entropy Estimation
• Quantum Algorithms for Testing Properties of Distributions
• Quantum speedup of Monte Carlo methods
• Span programs for functions with constant-sized 1-certificates
• Adiabatic Quantum State Generation
• Quantum Query Complexity of State Conversion
• Quantum cryptanalysis of hash and claw-free functions

This page was built for publication: Quantum Algorithms for Classical Probability Distributions