dorsal/arxiv
View SchemaSampling Fourier Transforms on Different Domains
| Authors | Lisa Hales, Sean Hallgren |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9812060 |
| URL | https://arxiv.org/abs/quant-ph/9812060 |
Abstract
We isolate and generalize a technique implicit in many quantum algorithms, including Shor's algorithms for factoring and discrete log. In particular, we show that the distribution sampled after a Fourier transform over ${\mathbb Z}_p$ can be efficiently approximated by transforming over ${\mathbb Z}_q$ for any q in a large range. Our result places no restrictions on the superposition to be transformed, generalizing the result implicit in Shor which applies only to periodic superpositions. In addition, our proof easily generalizes to multi-dimensional transforms for any constant number of dimensions.
{
"annotation_id": "d5c038ff-f638-4c09-86e6-d75edc4b3551",
"date_created": "2026-03-02T18:02:44.190000Z",
"date_modified": "2026-03-02T18:02:44.190000Z",
"file_hash": "34374b05c733d43be9597a03bdfe274e3afd269fffe551f0f43e248ee3fc0c66",
"private": false,
"record": {
"abstract": "We isolate and generalize a technique implicit in many quantum algorithms,\nincluding Shor\u0027s algorithms for factoring and discrete log. In particular, we\nshow that the distribution sampled after a Fourier transform over ${\\mathbb\nZ}_p$ can be efficiently approximated by transforming over ${\\mathbb Z}_q$ for\nany q in a large range. Our result places no restrictions on the superposition\nto be transformed, generalizing the result implicit in Shor which applies only\nto periodic superpositions. In addition, our proof easily generalizes to\nmulti-dimensional transforms for any constant number of dimensions.",
"arxiv_id": "quant-ph/9812060",
"authors": [
"Lisa Hales",
"Sean Hallgren"
],
"categories": [
"quant-ph"
],
"title": "Sampling Fourier Transforms on Different Domains",
"url": "https://arxiv.org/abs/quant-ph/9812060"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "e220deb8-457d-4647-b59c-46c539d62ac6",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}