Repository logo
 

Quantum conditional query complexity

Published version
Peer-reviewed

Change log

Authors

Sardharwalla, ISB 
Jozsa, R 

Abstract

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.

Description

Keywords

quantum query complexity, boolean functions, quantum oracle, quantum spectrum testing

Journal Title

Quantum Information and Computation

Conference Name

Journal ISSN

1533-7146

Volume Title

17

Publisher

Rinton Press

Publisher DOI

Sponsorship
EPSRC (1196264)
I.S.B.S. thanks EPSRC for financial support. S.S. acknowledges the support of Sidney Sussex College.