Show simple item record

dc.contributor.authorSardharwalla, Imdaden
dc.contributor.authorStrelchuk, Sergiien
dc.contributor.authorJozsa, Richarden
dc.date.accessioned2017-08-11T12:44:24Z
dc.date.available2017-08-11T12:44:24Z
dc.date.issued2017-06-01en
dc.identifier.issn1533-7146
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/266286
dc.description.abstractWe 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.
dc.description.sponsorshipI.S.B.S. thanks EPSRC for financial support. S.S. acknowledges the support of Sidney Sussex College.
dc.language.isoenen
dc.publisherRinton Press
dc.subjectquantum query complexityen
dc.subjectboolean functionsen
dc.subjectquantum oracleen
dc.subjectquantum spectrum testingen
dc.titleQuantum conditional query complexityen
dc.typeArticle
prism.endingPage567
prism.issueIdentifier7-8en
prism.publicationDate2017en
prism.publicationNameQuantum Information and Computationen
prism.startingPage541
prism.volume17en
dc.identifier.doi10.17863/CAM.12006
dcterms.dateAccepted2017-05-11en
rioxxterms.versionVoRen
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserveden
rioxxterms.licenseref.startdate2017-06-01en
dc.contributor.orcidSardharwalla, Imdad [0000-0002-0999-0464]
dc.contributor.orcidStrelchuk, Sergii [0000-0001-8390-3034]
dc.publisher.urlhttp://www.rintonpress.com/journals/qicabstracts/qicabstracts17-78.htmlen
rioxxterms.typeJournal Article/Reviewen
pubs.funder-project-idEPSRC (1196264)
dc.identifier.urlhttp://www.rintonpress.com/journals/qicabstracts/qicabstracts17-78.htmlen
cam.orpheus.successThu Jan 30 13:01:30 GMT 2020 - The item has an open VoR version.*
rioxxterms.freetoread.startdate2100-01-01


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record