Quantum conditional query complexity

We define and study a new type of quantum oracle, the quantum conditional oracle, which provides oracle access to the conditional probabilities associated with an underlying distribution. Amongst other properties, we (a) obtain speed-ups over the best known quantum algorithms for identity testing, equivalence testing and uniformity testing of probability distributions; (b) study the power of these oracles for testing properties of boolean functions, and obtain an algorithm for checking whether an $n$-input $m$-output boolean function is balanced or $\epsilon$-far from balanced; and (c) give a sub-linear algorithm, requiring $\tilde{O}(n^{3/4}/\epsilon)$ queries, for testing whether an $n$-dimensional quantum state is maximally mixed or not.

• Publication year

  2016

• Venue

  Quantum information & computation

• Publication date

  2016-09-01

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.26421/QIC17.7-8-1arXiv 1609.01600
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Probability An Introduction with

  2017cited by this paper
• Constraining the number of positive responses in adaptive, non-adaptive, and two-stage group testing

  2015cited by this paper
• Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing

  2015cited by this paper
• Quantum speedup of Monte Carlo methods

  2015cited by this paper
• Testing Probability Distributions Underlying Aggregated Data

  2014cited by this paper
• Testing Identity of Structured Distributions

  2014influential reference
• A Chasm Between Identity and Equivalence Testing with Conditional Queries

  2014cited by this paper
• Optimal Algorithms for Testing Closeness of Discrete Distributions

  2013cited by this paper
• A Survey of Quantum Property Testing

  2013cited by this paper
• Property Testing Lower Bounds via Communication Complexity

  2012cited by this paper
• Testing probability distributions using conditional samples

  2012influential reference
• On the power of conditional samples in distribution testing

  2012cited by this paper
• Property Testing Lower Bounds via Communication Complexity

  2011cited by this paper
• The Power of Linear Estimators

  2011cited by this paper
• New Results on Quantum Property Testing

  2010cited by this paper
• Property testing: current research and surveys

  2010cited by this paper
• Testing Closeness of Discrete Distributions

  2010cited by this paper
• Limitations on Quantum Dimensionality Reduction

  2010cited by this paper
• Quantum Algorithms for Testing Properties of Distributions

  2009influential reference
• Optimal Two-Stage Algorithms for Group Testing Problems

  2005cited by this paper
• Streaming and sublinear approximation of entropy and information distances

  2005influential reference
• Numerical Analysis: A Mathematical Introduction

  2002influential reference
• Testing random variables for independence and identity

  2001cited by this paper
• Introduction to Numerical Analysis

  2001cited by this paper
• Quantum algorithms revisited

  1997influential reference
• Property testing and its connection to learning and approximation

  1996cited by this paper
• Rapid solution of problems by quantum computation

  1992cited by this paper
• Random Generation of Combinatorial Structures from a Uniform Distribution

  1986cited by this paper
• Quantum theory and the bayesian inference problems

  1974cited by this paper
• A Remark on Stirling’s Formula

  1955cited by this paper

• Lifting Uniform Learners via Distributional Decomposition

  2023cites this paper
• Amplitude Ratios and Neural Network Quantum States

  2022cites this paper
• Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning

  2019cites this paper
• Modern challenges in distribution testing

  2018cites this paper
• Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing

  2018cites this paper
• Tradeoff Relations Between Accessible Information, Informational Power, and Purity

  2018cites this paper
• Estimating Quantum Entropy

  2017cites this paper