Attested & literatureAlgorithmsQuantum query algorithm2026-08-12

Testing properties of distributions given by sample oracles

distribution testingl1 distanceproperty testingquantum countingquery complexity

Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.

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.

Circuit & simulation

problem

encodetransform

algorithm

transformmeasure

readout

measure

What this takes and returns

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 →

How it works

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..

Implementation

FrameworkUnsupported

distribution-property-testing.txt

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.

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.

Declared gaps

Nobody has reviewed this record for gaps yet.

Literature & references

Quantum algorithms for testing properties of distributions2009 · Sergey Bravyi, Aram W. Harrow, Avinatan Hassidim

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).

arxiv.org/abs/0907.3920 ↗

Verification

Attested & literature

Peer-reviewed paper

Method: Curation only. The problem statement and speedup class were checked against the Quantum Algorithm Zoo's entry "Statistical Difference" (Oracular Algorithms); the primary reference's title, authors and submission year were read from its arXiv abs page; the complexity claim was taken from a clause of that paper's abstract (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."). No circuit was constructed, simulated or run.
Result: Pass · the record's problem, speedup class and primary reference agree with the two sources named above.
Caveat: This is a literature record: no oracle was instantiated, no distribution was sampled, and no circuit was built, compiled, simulated or run; no L1 distance was estimated here. Every figure above counts queries to the sample oracles, so none of it bounds gate count, circuit depth, qubit count, or the cost of building A and B for concrete distributions. The abstract writes approximately N^(1/2) rather than a bound with a stated constant, and it attaches that figure to a constant precision only: no dependence on an accuracy parameter ε is quoted by either source, so nothing above bounds the cost of a sharper estimate. The O(N^(1/3)) figure belongs to the Uniformity and Orthogonality tests, which the Zoo states as deciding approximate uniformity and orthogonality, and not to the L1-distance estimate. The classical Ω(N) and Ω(N^(1/2)) figures are recorded as the abstract states them, and are not re-derived here; the Zoo puts the classical side without asymptotic notation, as the number of necessary queries scaling essentially linearly with N, and this record does not treat that phrasing and the abstract's Ω(N) as the same statement. The Zoo's parameter T, the domain size of the two black boxes, appears in neither bound, so the cost above is stated in the range size N alone. That the main tool is the quantum counting algorithm is the Zoo's attribution to a paper outside this record, as is the further improved quantum algorithm the Zoo says was later obtained for this task.

Facts

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.
Secondary source for the speedup class: Quantum Algorithm Zoo — "Statistical Difference"
Section it is filed under: Oracular Algorithms
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

Source

Quantum algorithms for testing properties of distributions ↗

Kind: curated reference
Reviewed by: Leona Quantum curation pass
License: Citation metadata only; source publication terms apply