Finding Optimal Flows Efficiently
From MaRDI portal
Abstract: Among the models of quantum computation, the One-way Quantum Computer is one of the most promising proposals of physical realization, and opens new perspectives for parallelization by taking advantage of quantum entanglement. Since a one-way quantum computation is based on quantum measurement, which is a fundamentally nondeterministic evolution, a sufficient condition of global determinism has been introduced as the existence of a causal flow in a graph that underlies the computation. A O(n^3)-algorithm has been introduced for finding such a causal flow when the numbers of output and input vertices in the graph are equal, otherwise no polynomial time algorithm was known for deciding whether a graph has a causal flow or not. Our main contribution is to introduce a O(n^2)-algorithm for finding a causal flow, if any, whatever the numbers of input and output vertices are. This answers the open question stated by Danos and Kashefi and by de Beaudrap. Moreover, we prove that our algorithm produces an optimal flow (flow of minimal depth.) Whereas the existence of a causal flow is a sufficient condition for determinism, it is not a necessary condition. A weaker version of the causal flow, called gflow (generalized flow) has been introduced and has been proved to be a necessary and sufficient condition for a family of deterministic computations. Moreover the depth of the quantum computation is upper bounded by the depth of the gflow. However, the existence of a polynomial time algorithm that finds a gflow has been stated as an open question. In this paper we answer this positively with a polynomial time algorithm that outputs an optimal gflow of a given graph and thus finds an optimal correction strategy to the nondeterministic evolution due to measurements.
Recommendations
- An extremal result for geometries in the one-way measurement model
- Entanglement, flow and classical simulatability in measurement based quantum computation
- Optimization of one-way quantum computation measurement patterns
- Outcome determinism in measurement-based quantum computation with qudits
- Which Graph States are Useful for Quantum Information Processing?
Cited in
(20)- Optimization of one-way quantum computation measurement patterns
- Reversibility in extended measurement-based quantum computation
- Symmetry constraints on temporal order in measurement-based quantum computation
- Adiabatic graph-state quantum computation
- An extremal result for geometries in the one-way measurement model
- Unitary-circuit semantics for measurement-based computations
- scientific article; zbMATH DE number 641579 (Why is no real title available?)
- Automatic translation of quantum circuits to optimized one-way quantum computation patterns
- On weak odd domination and graph-based quantum secret sharing
- Pauli fusion: a computational model to realise quantum transformations from ZX terms
- Efficient Approximation of Flow Problems With Multiple Scales in Time
- Entanglement, flow and classical simulatability in measurement based quantum computation
- Quadratic Form Expansions for Unitaries
- Optimal quantum networks and one-shot entropies
- Outcome determinism in measurement-based quantum computation with qudits
- SOFSEM 2004: Theory and Practice of Computer Science
- Flow-preserving ZX-calculus Rewrite Rules for Optimisation and Obfuscation
- Relating measurement patterns to circuits via Pauli flow
- An algebraic formulation of Pauli flow, leading to faster flow-finding algorithms
- Pauli flow on open graphs with unknown measurement labels
This page was built for publication: Finding Optimal Flows Efficiently
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3521971)
