dorsal/arxiv
View SchemaAn extremal result for geometries in the one-way measurement model
| Authors | Niel de Beaudrap, Martin Pei |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0702229 |
| URL | https://arxiv.org/abs/quant-ph/0702229 |
Abstract
We present an extremal result for the class of graphs G which (together with some specified sets of input and output vertices, I and O) have a certain "flow" property introduced by Danos and Kashefi for the one-way measurement model of quantum computation. The existence of a flow for a triple (G,I,O) allows a unitary embedding to be derived from any choice of measurement bases allowed in the one-way measurement model. We prove an upper bound on the number of edges that a graph G may have, in order for a triple (G,I,O) to have a flow for some $I, O \subseteq V(G)$, in terms of the number of vertices in G and O. This implies that finding a flow for a triple (G,I,O) when |I| = |O| = k (corresponding to unitary transformations in the measurement model) and |V(G)| = n can be performed in time O(k^2 n), improving the earlier known bound of O(km) given in [quant-ph/0611284], where m = |E(G)|.
{
"annotation_id": "89e71c05-6471-40e4-b4a4-fbd7416bae8e",
"date_created": "2026-03-02T18:02:33.708000Z",
"date_modified": "2026-03-02T18:02:33.708000Z",
"file_hash": "121bfffbaf14d306c30be0d9d8edcbae304a3904acb901e51f53e2c69a444ee1",
"private": false,
"record": {
"abstract": "We present an extremal result for the class of graphs G which (together with\nsome specified sets of input and output vertices, I and O) have a certain\n\"flow\" property introduced by Danos and Kashefi for the one-way measurement\nmodel of quantum computation. The existence of a flow for a triple (G,I,O)\nallows a unitary embedding to be derived from any choice of measurement bases\nallowed in the one-way measurement model. We prove an upper bound on the number\nof edges that a graph G may have, in order for a triple (G,I,O) to have a flow\nfor some $I, O \\subseteq V(G)$, in terms of the number of vertices in G and O.\nThis implies that finding a flow for a triple (G,I,O) when |I| = |O| = k\n(corresponding to unitary transformations in the measurement model) and |V(G)|\n= n can be performed in time O(k^2 n), improving the earlier known bound of\nO(km) given in [quant-ph/0611284], where m = |E(G)|.",
"arxiv_id": "quant-ph/0702229",
"authors": [
"Niel de Beaudrap",
"Martin Pei"
],
"categories": [
"quant-ph"
],
"title": "An extremal result for geometries in the one-way measurement model",
"url": "https://arxiv.org/abs/quant-ph/0702229"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "cc484347-075e-4bf6-a3d9-2a71504c4453",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}