Algorithms · Quantum query algorithm
Testing properties of distributions given by sample oracles
Given oracle access to two unknown probability distributions P and Q on an N-element set — in the Zoo's setup, black boxes A and B whose domain is the integers 1 through T and whose range is the integers 1 through N, with the distribution over outputs induced by choosing uniformly at random among allowed inputs — approximate the L1 distance between the two distributions to constant precision.
Attested & literatureUpdated
- Record typeLiterature reference
- Speedup class (secondary source)Polynomial
- Primary source on the speedupNot checked against the primary source yet
- Reported costAbout N^(1/2) queries to estimate the L1 distance between P and Q with constant precision, where classical computers need Ω(N) queries; O(N^(1/3)) queries for testing Uniformity and Orthogonality, whose classical query complexity the abstract says is known to be Ω(N^(1/2)). The Zoo states the first figure as O(√N) and describes the classical requirement as scaling essentially linearly with N.
- Papers1
Given oracle access to two unknown probability distributions P and Q on an N-element set — in the Zoo's setup, black boxes A and B whose domain is the integers 1 through T and whose range is the integers 1 through N, with the distribution over outputs induced by choosing uniformly at random among allowed inputs — approximate the L1 distance between the two distributions to constant precision. Bravyi, Harrow and Hassidim pose the question as one of sample complexity in property testing: given oracles generating samples from two unknown distributions P and Q on an N-element set, how many samples are needed to test whether the two are close or far from each other in the L1 norm. Their paper studies quantum algorithms for testing properties of distributions, and it shows that the L1 distance can be estimated with constant precision using approximately N^(1/2) queries in the quantum setting, where classical computers need Ω(N). The paper also describes quantum algorithms for testing Uniformity and Orthogonality, at query complexity O(N^(1/3)) against a classical query complexity the abstract says is known to be Ω(N^(1/2)). The Zoo names the main tool behind these results as the quantum counting algorithm, and it records that a further improved quantum algorithm for this task has since been obtained in a paper outside this record.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
Bravyi, Harrow and Hassidim pose the question as one of sample complexity in property testing: given oracles generating samples from two unknown distributions P and Q on an N-element set, how many samples are needed to test whether the two are close or far from each other in the L1 norm. Their paper studies quantum algorithms for testing properties of distributions, and it shows that the L1 distance can be estimated with constant precision using approximately N^(1/2) queries in the quantum setting, where classical computers need Ω(N). The paper also describes quantum algorithms for testing Uniformity and Orthogonality, at query complexity O(N^(1/3)) against a classical query complexity the abstract says is known to be Ω(N^(1/2)). The Zoo names the main tool behind these results as the quantum counting algorithm, and it records that a further improved quantum algorithm for this task has since been obtained in a paper outside this record. This record's speedup class, "Polynomial", is a secondary source's classification of the oracular algorithms it files this under — not a claim its primary paper makes. Not checked against the primary source yet. Reported cost: About N^(1/2) queries to estimate the L1 distance between P and Q with constant precision, where classical computers need Ω(N) queries; O(N^(1/3)) queries for testing Uniformity and Orthogonality, whose classical query complexity the abstract says is known to be Ω(N^(1/2)). The Zoo states the first figure as O(√N) and describes the classical requirement as scaling essentially linearly with N..
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Record type
- Literature reference
- Speedup class (secondary source)
- Polynomial
- Primary source on the speedup
- Not checked against the primary source yet
- Reported cost
- About N^(1/2) queries to estimate the L1 distance between P and Q with constant precision, where classical computers need Ω(N) queries; O(N^(1/3)) queries for testing Uniformity and Orthogonality, whose classical query complexity the abstract says is known to be Ω(N^(1/2)). The Zoo states the first figure as O(√N) and describes the classical requirement as scaling essentially linearly with N.
- Speedup class
- Polynomial (not yet checked against the record's own primary paper)
- Complexity basis
- abstract of arXiv:0907.3920, with \Omega rendered into Unicode as Ω: "It is shown that the L_1-distance between P and Q can be estimated with a constant precision using approximately N^{1/2} queries in the quantum settings, whereas classical computers need Ω(N) queries", and "We also describe quantum algorithms for testing Uniformity and Orthogonality with query complexity O(N^{1/3}). The classical query complexity of these problems is known to be Ω(N^{1/2})."; Quantum Algorithm Zoo entry "Statistical Difference", quoted in clauses that omit the entry reference numerals, with the inline-math delimiters \( \) stripped and \sqrt{N} rendered into Unicode as √N: "Classically the number of necessary queries scales essentially linearly with N", "a quantum computer can achieve this using O(√N) queries", and "Approximate uniformity and orthogonality of probability distributions can also be decided on a quantum computer using O(N^{1/3}) queries."
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Quantum query algorithm with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
ALGORITHM: Testing properties of distributions given by sample oracles
PROBLEM: Given oracle access to two unknown probability distributions P and Q on an N-element set — in the Zoo's setup, black boxes A and B whose domain is the integers 1 through T and whose range is the integers 1 through N, with the distribution over outputs induced by choosing uniformly at random among allowed inputs — approximate the L1 distance between the two distributions to constant precision.
IDEA: Bravyi, Harrow and Hassidim pose the question as one of sample complexity in property testing: given oracles generating samples from two unknown distributions P and Q on an N-element set, how many samples are needed to test whether the two are close or far from each other in the L1 norm. Their paper studies quantum algorithms for testing properties of distributions, and it shows that the L1 distance can be estimated with constant precision using approximately N^(1/2) queries in the quantum setting, where classical computers need Ω(N). The paper also describes quantum algorithms for testing Uniformity and Orthogonality, at query complexity O(N^(1/3)) against a classical query complexity the abstract says is known to be Ω(N^(1/2)). The Zoo names the main tool behind these results as the quantum counting algorithm, and it records that a further improved quantum algorithm for this task has since been obtained in a paper outside this record.
REPORTED COST: About N^(1/2) queries to estimate the L1 distance between P and Q with constant precision, where classical computers need Ω(N) queries; O(N^(1/3)) queries for testing Uniformity and Orthogonality, whose classical query complexity the abstract says is known to be Ω(N^(1/2)). The Zoo states the first figure as O(√N) and describes the classical requirement as scaling essentially linearly with N.
BASIS: abstract of arXiv:0907.3920, with \Omega rendered into Unicode as Ω: "It is shown that the L_1-distance between P and Q can be estimated with a constant precision using approximately N^{1/2} queries in the quantum settings, whereas classical computers need Ω(N) queries", and "We also describe quantum algorithms for testing Uniformity and Orthogonality with query complexity O(N^{1/3}). The classical query complexity of these problems is known to be Ω(N^{1/2})."; Quantum Algorithm Zoo entry "Statistical Difference", quoted in clauses that omit the entry reference numerals, with the inline-math delimiters \( \) stripped and \sqrt{N} rendered into Unicode as √N: "Classically the number of necessary queries scales essentially linearly with N", "a quantum computer can achieve this using O(√N) queries", and "Approximate uniformity and orthogonality of probability distributions can also be decided on a quantum computer using O(N^{1/3}) queries."
PRIMARY SOURCE: Sergey Bravyi, Aram W. Harrow, Avinatan Hassidim (2009), Quantum algorithms for testing properties of distributions — https://arxiv.org/abs/0907.3920
This is a literature reference record, not an executable circuit.A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Related entries
- Quantum counting
Algorithms
- Quantum amplitude estimation
Algorithms
- Element distinctness by quantum walk
Algorithms
References
- Quantum algorithms for testing properties of distributions
Sergey Bravyi, Aram W. Harrow, Avinatan Hassidim · 2009
Primary source: it states the approximately N^(1/2)-query estimate of the L1 distance at constant precision against Ω(N) classically, and the O(N^(1/3))-query tests for Uniformity and Orthogonality against a classical Ω(N^(1/2)). Consult it for the sample-oracle model it assumes, for how the Uniformity and Orthogonality properties are defined, and for the constants and success probabilities the abstract leaves out of approximately N^(1/2).