dorsal/arxiv
View SchemaOn Statistical Query Sampling and NMR Quantum Computing
| Authors | Avrim Blum, Ke Yang |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0307071 |
| URL | https://arxiv.org/abs/quant-ph/0307071 |
| DOI | 10.1109/CCC.2003.1214420 |
Abstract
We introduce a ``Statistical Query Sampling'' model, in which the goal of an algorithm is to produce an element in a hidden set $Ssubseteqbit^n$ with reasonable probability. The algorithm gains information about $S$ through oracle calls (statistical queries), where the algorithm submits a query function $g(cdot)$ and receives an approximation to $Pr_{x in S}[g(x)=1]$. We show how this model is related to NMR quantum computing, in which only statistical properties of an ensemble of quantum systems can be measured, and in particular to the question of whether one can translate standard quantum algorithms to the NMR setting without putting all of their classical post-processing into the quantum system. Using Fourier analysis techniques developed in the related context of {em statistical query learning}, we prove a number of lower bounds (both information-theoretic and cryptographic) on the ability of algorithms to produces an $xin S$, even when the set $S$ is fairly simple. These lower bounds point out a difficulty in efficiently applying NMR quantum computing to algorithms such as Shor's and Simon's algorithm that involve significant classical post-processing. We also explicitly relate the notion of statistical query sampling to that of statistical query learning. An extended abstract appeared in the 18th Aunnual IEEE Conference of Computational Complexity (CCC 2003), 2003. Keywords: statistical query, NMR quantum computing, lower bound
{
"annotation_id": "b1da91a6-7a34-4f82-b4d6-da9afa5fb007",
"date_created": "2026-03-02T18:01:59.975000Z",
"date_modified": "2026-03-02T18:01:59.975000Z",
"file_hash": "ceda68eb00abb45058e6ee0127bcf93d3be82426823d1dda9b8c777a7f1de32c",
"private": false,
"record": {
"abstract": "We introduce a ``Statistical Query Sampling\u0027\u0027 model, in which the goal of an\nalgorithm is to produce an element in a hidden set $Ssubseteqbit^n$ with\nreasonable probability. The algorithm gains information about $S$ through\noracle calls (statistical queries), where the algorithm submits a query\nfunction $g(cdot)$ and receives an approximation to $Pr_{x in S}[g(x)=1]$. We\nshow how this model is related to NMR quantum computing, in which only\nstatistical properties of an ensemble of quantum systems can be measured, and\nin particular to the question of whether one can translate standard quantum\nalgorithms to the NMR setting without putting all of their classical\npost-processing into the quantum system. Using Fourier analysis techniques\ndeveloped in the related context of {em statistical query learning}, we prove a\nnumber of lower bounds (both information-theoretic and cryptographic) on the\nability of algorithms to produces an $xin S$, even when the set $S$ is fairly\nsimple. These lower bounds point out a difficulty in efficiently applying NMR\nquantum computing to algorithms such as Shor\u0027s and Simon\u0027s algorithm that\ninvolve significant classical post-processing. We also explicitly relate the\nnotion of statistical query sampling to that of statistical query learning.\n An extended abstract appeared in the 18th Aunnual IEEE Conference of\nComputational Complexity (CCC 2003), 2003.\n Keywords: statistical query, NMR quantum computing, lower bound",
"arxiv_id": "quant-ph/0307071",
"authors": [
"Avrim Blum",
"Ke Yang"
],
"categories": [
"quant-ph"
],
"doi": "10.1109/CCC.2003.1214420",
"title": "On Statistical Query Sampling and NMR Quantum Computing",
"url": "https://arxiv.org/abs/quant-ph/0307071"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "2584d6c2-090b-456f-92c9-ba78c5a2b576",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}