Determinism and computational power of real measurement-based quantum computation

DOI10.1007/978-3-662-55751-8_31zbMATH Open1495.81032arXiv1610.02824OpenAlexW2529886305MaRDI QIDQ1679995FDOQ1679995

Authors: Simon Perdrix, Luc Sanselme 

Publication date: 22 November 2017

Abstract: Measurement-based quantum computing (MBQC) is a universal model for quantum computation. The combinatorial characterisation of determinism in this model, powered by measurements, and hence, fundamentally probabilistic, is the cornerstone of most of the breakthrough results in this field. The most general known sufficient condition for a deterministic MBQC to be driven is that the underlying graph of the computation has a particular kind of flow called Pauli flow. The necessity of the Pauli flow was an open question. We show that the Pauli flow is necessary for real-MBQC, and not in general providing counterexamples for (complex) MBQC. We explore the consequences of this result for real MBQC and its applications. Real MBQC and more generally real quantum computing is known to be universal for quantum computing. Real MBQC has been used for interactive proofs by McKague. The two-prover case corresponds to real-MBQC on bipartite graphs. While (complex) MBQC on bipartite graphs are universal, the universality of real MBQC on bipartite graphs was an open question. We show that real bipartite MBQC is not universal proving that all measurements of real bipartite MBQC can be parallelised leading to constant depth computations. As a consequence, McKague techniques cannot lead to two-prover interactive proofs.

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

Recommendations

• Outcome determinism in measurement-based quantum computation with qudits
• Quantum logic as a consequence of realistic measurements on deterministic systems
• QUANTUM COMPUTATION BY MEASUREMENTS
• Measurement-based quantum computation and undecidable logic
• Universal quantum computation on the power of quantum non-demolition measurements
• The Role of Classical Computation in Measurement-Based Quantum Computation
• Computational Depth Complexity of Measurement-Based Quantum Computation
• The power of various real-valued quantum queries
• ON THE POWER QUANTUM COMPUTATION OVER REAL HILBERT SPACES
• scientific article; zbMATH DE number 1139335

Mathematics Subject Classification ID

Quantum computation (81P68)

Cited In (9)

• Boolean powers and quantum measurements
• Title not available (Why is that?)
• Reversibility in extended measurement-based quantum computation
• Hierarchies of resources for measurement-based quantum computation
• Measurement-based quantum computation cannot avoid byproducts
• Y-calculus: a language for real matrices derived from the ZX-calculus
• ON THE POWER QUANTUM COMPUTATION OVER REAL HILBERT SPACES
• Outcome determinism in measurement-based quantum computation with qudits
• Relating measurement patterns to circuits via Pauli flow

This page was built for publication: Determinism and computational power of real measurement-based quantum computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1679995)