Finding Optimal Flows Efficiently

DOI10.1007/978-3-540-70575-8_70MaRDI QIDQ3521971zbMATH OpenOpenAlexFDO

Authors Mehdi Mhalla, Simon Perdrix

Publication date 28 August 2008

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0709.2670

Mathematics Subject Classification ID

Quantum computation (81P68)

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

(18)

• scientific article; zbMATH DE number 641579 (Why is no real title available?)
• Entanglement, flow and classical simulatability in measurement based quantum computation
• An extremal result for geometries in the one-way measurement model
• scientific article; zbMATH DE number 7453176 (Why is no real title available?)
• Reversibility in extended measurement-based quantum computation
• Symmetry constraints on temporal order in measurement-based quantum computation
• Quadratic Form Expansions for Unitaries
• Outcome determinism in measurement-based quantum computation with qudits
• Adiabatic graph-state quantum computation
• SOFSEM 2004: Theory and Practice of Computer Science
• Flow-preserving ZX-calculus Rewrite Rules for Optimisation and Obfuscation
• Automatic translation of quantum circuits to optimized one-way quantum computation patterns
• Relating measurement patterns to circuits via Pauli flow
• On weak odd domination and graph-based quantum secret sharing
• Unitary-circuit semantics for measurement-based computations
• Efficient Approximation of Flow Problems With Multiple Scales in Time
• Optimization of one-way quantum computation measurement patterns
• Optimal quantum networks and one-shot entropies

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)