dorsal/arxiv
View SchemaQuantum Arithmetic on Galois Fields
| Authors | Stephane Beauregard, Gilles Brassard, Jose M. Fernandez |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0301163 |
| URL | https://arxiv.org/abs/quant-ph/0301163 |
Abstract
In this paper we discuss the problem of performing elementary finite field arithmetic on a quantum computer. Of particular interest, is the controlled-multiplication operation, which is the only group-specific operation in Shor's algorithms for factoring and solving the Discrete Log Problem. We describe how to build quantum circuits for performing this operation on the generic Galois fields GF($p^k$), as well as the boundary cases GF($p$) and GF($2^k$). We give the detailed size, width and depth complexity of such circuits, which ultimately will allow us to obtain detailed upper bounds on the amount of quantum resources needed to solve instances of the DLP on such fields.
{
"annotation_id": "4b865be6-a8fd-467d-84dd-ce0793d788cb",
"date_created": "2026-03-02T18:01:55.598000Z",
"date_modified": "2026-03-02T18:01:55.598000Z",
"file_hash": "598c9f559f702e933d83e7092ebd38c35a340ce39285c645773c20da787ae227",
"private": false,
"record": {
"abstract": "In this paper we discuss the problem of performing elementary finite field\narithmetic on a quantum computer. Of particular interest, is the\ncontrolled-multiplication operation, which is the only group-specific operation\nin Shor\u0027s algorithms for factoring and solving the Discrete Log Problem. We\ndescribe how to build quantum circuits for performing this operation on the\ngeneric Galois fields GF($p^k$), as well as the boundary cases GF($p$) and\nGF($2^k$). We give the detailed size, width and depth complexity of such\ncircuits, which ultimately will allow us to obtain detailed upper bounds on the\namount of quantum resources needed to solve instances of the DLP on such\nfields.",
"arxiv_id": "quant-ph/0301163",
"authors": [
"Stephane Beauregard",
"Gilles Brassard",
"Jose M. Fernandez"
],
"categories": [
"quant-ph"
],
"title": "Quantum Arithmetic on Galois Fields",
"url": "https://arxiv.org/abs/quant-ph/0301163"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "9150994f-fe71-4997-95e3-8b806d673000",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}