dorsal/arxiv
View SchemaPolarization Requirements for Ensemble Implementations of Quantum Algorithms with a Single Bit Output
| Authors | Brandon M. Anderson, David Collins |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0508061 |
| URL | https://arxiv.org/abs/quant-ph/0508061 |
| DOI | 10.1103/PhysRevA.72.042337 |
Abstract
We compare the failure probabilities of ensemble implementations of quantum algorithms which use pseudo-pure initial states, quantified by their polarization, to those of competing classical probabilistic algorithms. Specifically we consider a class algorithms which require only one bit to output the solution to problems. For large ensemble sizes, we present a general scheme to determine a critical polarization beneath which the quantum algorithm fails with greater probability than its classical competitor. We apply this to the Deutsch-Jozsa algorithm and show that the critical polarization is 86.6%.
{
"annotation_id": "5f1e211b-e3d5-4e63-92b6-0f8eac96d6d3",
"date_created": "2026-03-02T18:02:19.404000Z",
"date_modified": "2026-03-02T18:02:19.404000Z",
"file_hash": "1ade4878760e9ade41740cc29055cc3f02e72aa2a71478993528860372ade278",
"private": false,
"record": {
"abstract": "We compare the failure probabilities of ensemble implementations of quantum\nalgorithms which use pseudo-pure initial states, quantified by their\npolarization, to those of competing classical probabilistic algorithms.\nSpecifically we consider a class algorithms which require only one bit to\noutput the solution to problems. For large ensemble sizes, we present a general\nscheme to determine a critical polarization beneath which the quantum algorithm\nfails with greater probability than its classical competitor. We apply this to\nthe Deutsch-Jozsa algorithm and show that the critical polarization is 86.6%.",
"arxiv_id": "quant-ph/0508061",
"authors": [
"Brandon M. Anderson",
"David Collins"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.72.042337",
"title": "Polarization Requirements for Ensemble Implementations of Quantum Algorithms with a Single Bit Output",
"url": "https://arxiv.org/abs/quant-ph/0508061"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "a9f90c44-9472-4e46-8e72-d38ceb838c76",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}