dorsal/arxiv
View SchemaQuantum algorithms for solvable groups
| Authors | John Watrous |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0011023 |
| URL | https://arxiv.org/abs/quant-ph/0011023 |
Abstract
In this paper we give a polynomial-time quantum algorithm for computing orders of solvable groups. Several other problems, such as testing membership in solvable groups, testing equality of subgroups in a given solvable group, and testing normality of a subgroup in a given solvable group, reduce to computing orders of solvable groups and therefore admit polynomial-time quantum algorithms as well. Our algorithm works in the setting of black-box groups, wherein none of these problems can be computed classically in polynomial time. As an important byproduct, our algorithm is able to produce a pure quantum state that is uniform over the elements in any chosen subgroup of a solvable group, which yields a natural way to apply existing quantum algorithms to factor groups of solvable groups.
{
"annotation_id": "e4f0df1b-f259-4787-83af-9e3551f6fc33",
"date_created": "2026-03-02T18:01:42.593000Z",
"date_modified": "2026-03-02T18:01:42.593000Z",
"file_hash": "7e2a41f7ce611be8965004c9f4d1e7f2d6663ffc827b9ed8c8c7d2727e6140f4",
"private": false,
"record": {
"abstract": "In this paper we give a polynomial-time quantum algorithm for computing\norders of solvable groups. Several other problems, such as testing membership\nin solvable groups, testing equality of subgroups in a given solvable group,\nand testing normality of a subgroup in a given solvable group, reduce to\ncomputing orders of solvable groups and therefore admit polynomial-time quantum\nalgorithms as well. Our algorithm works in the setting of black-box groups,\nwherein none of these problems can be computed classically in polynomial time.\nAs an important byproduct, our algorithm is able to produce a pure quantum\nstate that is uniform over the elements in any chosen subgroup of a solvable\ngroup, which yields a natural way to apply existing quantum algorithms to\nfactor groups of solvable groups.",
"arxiv_id": "quant-ph/0011023",
"authors": [
"John Watrous"
],
"categories": [
"quant-ph"
],
"title": "Quantum algorithms for solvable groups",
"url": "https://arxiv.org/abs/quant-ph/0011023"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "5ac233ce-1a9d-47b5-9d73-5b5dfdf5519d",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}