Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0603266

Phase map decompositions for unitaries

Niel de Beaudrap, Vincent Danos A, Elham Kashefi

Published Mar 29, 2006• 14 citations
arXivHTMLPDF

Abstract

We propose a universal decomposition of unitary maps over a tensorial power of C^2, introducing the key concept of "phase maps", and investigate how this decomposition can be used to implement unitary maps directly in the measurement-based model for quantum computing. Specifically, we show how to extract from such a decomposition a matching entangled graph state (with inputs), and a set of measurements angles, when there is one. Next, we check whether the obtained graph state verifies a "flow" condition, which guarantees an execution order such that the dependent measurements and corrections of the pattern yield deterministic results. Using a graph theoretic characterization of flows, we can determine whether a flow can be constructed for a graph state in polynomial time. This approach yields an algorithmic procedure which, when it succeeds, may produce an efficient pattern for a given unitary.

DOI
10.48550/arxiv.quant-ph/0603266

Related papers

Finding flows in the one-way measurement model

Niel de Beaudrap

The one-way measurement model is a framework for universal quantum computation in which algorithms are partially described by a graph $G$ of entanglement relations on a collection of qubits. A sufficient condition for an algorithm to perform a unitary embedding between two Hilbert spaces is for the graph $G$, together with input and output $\mathit{I}$, $\mathit{O}$ vertices $I,O\ensuremath{\subseteq}V(G)$, to have a flow in the sense introduced by Danos and Kashefi [Phys. Rev. A 74, 052310 (2006)]. For the special case of $|I|=|O|$, using a graph-theoretic characterization, I show that such flows are unique when they exist. This leads to an efficient algorithm for finding flows by a reduction to solved problems in graph theory.

arXiv:quant-ph/0611284•Physical Review A•Feb 29, 2008•25 citations

Extended phase map decompositions for unitaries

Vedran Dunjko, Elham Kashefi

We give a complete structural characterisation of the map implemented by the positive branch of a one-way pattern. Our approach is based on the phase map decomposition (de Beaudrap et al. 2006; de Beaudrap et al. 2008) and leads to some preliminary results on the connection between the column structure of a given unitary and the angles of measurements in a pattern that implements it. Our characterisation highlights the role of entanglement in the efficiency of the simulation of a one-way pattern, and it is a step forward towards a full characterisation of those unitaries that have an efficient one-way model implementation.

Mathematical Structures in Computer Science•Feb 28, 2013•0 citations

Determinism in the one-way model

Vincent Danos A, Elham Kashefi

We introduce a flow condition on open graph states (graph states with inputs and outputs) which guarantees globally deterministic behavior of a class of measurement patterns defined over them. Dependent Pauli corrections are derived for all such patterns, which equalize all computation branches, and only depend on the underlying entanglement graph and its choice of inputs and outputs. The class of patterns having flow is stable under composition and tensorization, and has unitary embeddings as realizations. The restricted class of patterns having both flow and reverse flow supports an operation of adjunction, and has all and only unitaries as realizations.

arXiv:quant-ph/0506062•Physical Review A•Nov 8, 2006•145 citations

Working with measurement-based computations on qudits

Piotr Mitosek, Miriam Backens

Measurement-based quantum computing is a universal model of quantum computation in which successive product measurements of an entangled resource state drive the computation. The non-deterministic nature of measurements necessitates adaptivity to ensure an overall deterministic computation. Flow structures characterise cases in which such an adaptive correction procedure is possible. Recently, flow has been defined in a setting where the resource states are prime-dimensional qudit graph states rather than the usual qubit graph states. Yet, this qudit flow definition is more burdensome to work with than analogous definitions for qubits. Here, we give a simpler definition of qudit flow and consider various useful properties of this flow, drawing on results for the qubit case. In particular, we show how to focus qudit flow and argue that focused flow is canonical. We improve the previous algebraic formulation to capture focused flow and use it to obtain an $O(n^3)$ flow-finding algorithm (where $n$ is the number of qudits), matching the best known complexity for qubit flows and improving on the previous $O(n^4)$ result for qudits. Furthermore, we explore multiple flow-preserving transformations, thus opening a pathway to using flow for optimisation. These transformations include pivoting, removal and insertion of certain types of vertices, and reversibility of flow. Lastly, we propose an algorithmic approach to generating large qudit computations with flow, for testing or machine learning.

quant-pharXiv:2606.30525•Jun 30, 2026•0 citations

Theory of measurement-based quantum computing

Niel de Beaudrap

In the study of quantum computation, data is represented in terms of linear operators which form a generalized model of probability, and computations are most commonly described as products of unitary transformations, which are the transformations which preserve the quality of the data in a precise sense. This naturally leads to "unitary circuit models", which are models of computation in which unitary operators are expressed as a product of "elementary" unitary transformations. However, unitary transformations can also be effected as a composition of operations which are not all unitary themselves: the "one-way measurement model" is one such model of quantum computation. In this thesis, we examine the relationship between representations of unitary operators and decompositions of those operators in the one-way measurement model. In particular, we consider different circumstances under which a procedure in the one-way measurement model can be described as simulating a unitary circuit, by considering the combinatorial structures which are common to unitary circuits and two simple constructions of one-way based procedures. These structures lead to a characterization of the one-way measurement patterns which arise from these constructions, which can then be related to efficiently testable properties of graphs. We also consider how these characterizations provide automatic techniques for obtaining complete measurement-based decompositions, from unitary transformations which are specified by operator expressions bearing a formal resemblance to path integrals. These techniques are presented as a possible means to devise new algorithms in the one-way measurement model, independently of algorithms in the unitary circuit model.

arXiv:0812.2869•Dec 15, 2008•0 citations

Efficient quantum pseudorandomness with simple graph states

Rawad Mezher, Joe Ghalbouni, Joseph Dgheim +1 more

Measurement based (MB) quantum computation allows for universal quantum computing by measuring individual qubits prepared in entangled multipartite states, known as graph states. Unless corrected for, the randomness of the measurements leads to the generation of ensembles of random unitaries, where each random unitary is identified with a string of possible measurement results. We show that repeating an MB scheme an efficient number of times, on a simple graph state, with measurements at fixed angles and no feedforward corrections, produces a random unitary ensemble that is an $\ensuremath{\varepsilon}$-approximate $t$ design on $n$ qubits. Unlike previous constructions, the graph is regular and is also a universal resource for measurement based quantum computing, closely related to the brickwork state.

arXiv:1709.08091•Physical Review A•Feb 23, 2018•24 citations
We propose a universal decomposition of unitary maps over a tensorial power of C^2, introducing the key concept of "phase maps", and investigate how this decomposition can be used to implement unitary maps directly in the measurement-based model for quantum computing. Specifically, we show how to extract from such a decomposition a matching entangled graph state (with inputs), and a set of measurements angles, when there is one. Next, we check whether the obtained graph state verifies a "flow" condition, which guarantees an execution order such that the dependent measurements and corrections of the pattern yield deterministic results. Using a graph theoretic characterization of flows, we can determine whether a flow can be constructed for a graph state in polynomial time. This approach yields an algorithmic procedure which, when it succeeds, may produce an efficient pattern for a given unitary.
The one-way measurement model is a framework for universal quantum computation in which algorithms are partially described by a graph GGG of entanglement relations on a collection of qubits. A sufficient condition for an algorithm to perform a unitary embedding between two Hilbert spaces is for the graph GGG, together with input and output I\mathit{I}I, O\mathit{O}O vertices $I,O\ensuremath{\subseteq}V(G)$, to have a flow in the sense introduced by Danos and Kashefi [Phys. Rev. A 74, 052310 (2006)]. For the special case of ∣I∣=∣O∣|I|=|O|∣I∣=∣O∣, using a graph-theoretic characterization, I show that such flows are unique when they exist. This leads to an efficient algorithm for finding flows by a reduction to solved problems in graph theory.
We give a complete structural characterisation of the map implemented by the positive branch of a one-way pattern. Our approach is based on the phase map decomposition (de Beaudrap et al. 2006; de Beaudrap et al. 2008) and leads to some preliminary results on the connection between the column structure of a given unitary and the angles of measurements in a pattern that implements it. Our characterisation highlights the role of entanglement in the efficiency of the simulation of a one-way pattern, and it is a step forward towards a full characterisation of those unitaries that have an efficient one-way model implementation.
We introduce a flow condition on open graph states (graph states with inputs and outputs) which guarantees globally deterministic behavior of a class of measurement patterns defined over them. Dependent Pauli corrections are derived for all such patterns, which equalize all computation branches, and only depend on the underlying entanglement graph and its choice of inputs and outputs. The class of patterns having flow is stable under composition and tensorization, and has unitary embeddings as realizations. The restricted class of patterns having both flow and reverse flow supports an operation of adjunction, and has all and only unitaries as realizations.
Measurement-based quantum computing is a universal model of quantum computation in which successive product measurements of an entangled resource state drive the computation. The non-deterministic nature of measurements necessitates adaptivity to ensure an overall deterministic computation. Flow structures characterise cases in which such an adaptive correction procedure is possible. Recently, flow has been defined in a setting where the resource states are prime-dimensional qudit graph states rather than the usual qubit graph states. Yet, this qudit flow definition is more burdensome to work with than analogous definitions for qubits. Here, we give a simpler definition of qudit flow and consider various useful properties of this flow, drawing on results for the qubit case. In particular, we show how to focus qudit flow and argue that focused flow is canonical. We improve the previous algebraic formulation to capture focused flow and use it to obtain an O(n3)O(n^3)O(n3) flow-finding algorithm (where nnn is the number of qudits), matching the best known complexity for qubit flows and improving on the previous O(n4)O(n^4)O(n4) result for qudits. Furthermore, we explore multiple flow-preserving transformations, thus opening a pathway to using flow for optimisation. These transformations include pivoting, removal and insertion of certain types of vertices, and reversibility of flow. Lastly, we propose an algorithmic approach to generating large qudit computations with flow, for testing or machine learning.
In the study of quantum computation, data is represented in terms of linear operators which form a generalized model of probability, and computations are most commonly described as products of unitary transformations, which are the transformations which preserve the quality of the data in a precise sense. This naturally leads to "unitary circuit models", which are models of computation in which unitary operators are expressed as a product of "elementary" unitary transformations. However, unitary transformations can also be effected as a composition of operations which are not all unitary themselves: the "one-way measurement model" is one such model of quantum computation. In this thesis, we examine the relationship between representations of unitary operators and decompositions of those operators in the one-way measurement model. In particular, we consider different circumstances under which a procedure in the one-way measurement model can be described as simulating a unitary circuit, by considering the combinatorial structures which are common to unitary circuits and two simple constructions of one-way based procedures. These structures lead to a characterization of the one-way measurement patterns which arise from these constructions, which can then be related to efficiently testable properties of graphs. We also consider how these characterizations provide automatic techniques for obtaining complete measurement-based decompositions, from unitary transformations which are specified by operator expressions bearing a formal resemblance to path integrals. These techniques are presented as a possible means to devise new algorithms in the one-way measurement model, independently of algorithms in the unitary circuit model.
Measurement based (MB) quantum computation allows for universal quantum computing by measuring individual qubits prepared in entangled multipartite states, known as graph states. Unless corrected for, the randomness of the measurements leads to the generation of ensembles of random unitaries, where each random unitary is identified with a string of possible measurement results. We show that repeating an MB scheme an efficient number of times, on a simple graph state, with measurements at fixed angles and no feedforward corrections, produces a random unitary ensemble that is an $\ensuremath{\varepsilon}$-approximate ttt design on nnn qubits. Unlike previous constructions, the graph is regular and is also a universal resource for measurement based quantum computing, closely related to the brickwork state.