dorsal/arxiv
View SchemaQuantum Computing and Hidden Variables I: Mapping Unitary to Stochastic Matrices
| Authors | Scott Aaronson |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0408035 |
| URL | https://arxiv.org/abs/quant-ph/0408035 |
| DOI | 10.1103/PhysRevA.71.032325 |
Abstract
This paper initiates the study of hidden variables from the discrete, abstract perspective of quantum computing. For us, a hidden-variable theory is simply a way to convert a unitary matrix that maps one quantum state to another, into a stochastic matrix that maps the initial probability distribution to the final one in some fixed basis. We list seven axioms that we might want such a theory to satisfy, and then investigate which of the axioms can be satisfied simultaneously. Toward this end, we construct a new hidden-variable theory that is both robust to small perturbations and indifferent to the identity operation, by exploiting an unexpected connection between unitary matrices and network flows. We also analyze previous hidden-variable theories of Dieks and Schrodinger in terms of our axioms. In a companion paper, we will show that actually sampling the history of a hidden variable under reasonable axioms is at least as hard as solving the Graph Isomorphism problem; and indeed is probably intractable even for quantum computers.
{
"annotation_id": "b7c19d23-a2be-46f1-8faf-e4b44656318e",
"date_created": "2026-03-02T18:02:09.997000Z",
"date_modified": "2026-03-02T18:02:09.997000Z",
"file_hash": "4837f2b1020e2263e60bb31f802a5a61d027d4e5756aa81489faad43dc1e414c",
"private": false,
"record": {
"abstract": "This paper initiates the study of hidden variables from the discrete,\nabstract perspective of quantum computing. For us, a hidden-variable theory is\nsimply a way to convert a unitary matrix that maps one quantum state to\nanother, into a stochastic matrix that maps the initial probability\ndistribution to the final one in some fixed basis. We list seven axioms that we\nmight want such a theory to satisfy, and then investigate which of the axioms\ncan be satisfied simultaneously. Toward this end, we construct a new\nhidden-variable theory that is both robust to small perturbations and\nindifferent to the identity operation, by exploiting an unexpected connection\nbetween unitary matrices and network flows. We also analyze previous\nhidden-variable theories of Dieks and Schrodinger in terms of our axioms. In a\ncompanion paper, we will show that actually sampling the history of a hidden\nvariable under reasonable axioms is at least as hard as solving the Graph\nIsomorphism problem; and indeed is probably intractable even for quantum\ncomputers.",
"arxiv_id": "quant-ph/0408035",
"authors": [
"Scott Aaronson"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.71.032325",
"title": "Quantum Computing and Hidden Variables I: Mapping Unitary to Stochastic Matrices",
"url": "https://arxiv.org/abs/quant-ph/0408035"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "ea8669fd-643d-447a-8256-8d803f5d888d",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}