CUED Publications database

Quantum conditional query complexity

Sardharwalla, ISB and Strelchuk, S and Jozsa, R (2017) Quantum conditional query complexity. Quantum Information and Computation, 17. pp. 541-567. ISSN 1533-7146

Full text not available from this repository.


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 highly efficient 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 ϵ-far from balanced; and (c) give an algorithm, requiring Õ(n/ϵ) queries, for testing whether an n-dimensional quantum state is maximally mixed or not.

Item Type: Article
Uncontrolled Keywords: quantum query complexity boolean functions quantum oracle quantum spectrum testing
Depositing User: Cron Job
Date Deposited: 19 Jun 2019 20:18
Last Modified: 15 Apr 2021 05:11