Characterising Determinism in MBQCs involving Pauli Measurements

• URL: http://arxiv.org/abs/2207.09368v3
• Date: Fri, 15 Nov 2024 16:51:10 GMT
• Title: Characterising Determinism in MBQCs involving Pauli Measurements
• Authors: Mehdi Mhalla, Simon Perdrix, Luc Sanselme,
• Abstract summary: We introduce a new characterisation of determinism in Measurement-Based Quantum Computing. The ability to perform an overall deterministic computation requires a correction strategy because of the non-determinism of each measurement. We show that Pauli flow is actually necessary for robust determinism in a weaker sense.
• Score: 0.8192907805418583
• License:
• Abstract: We introduce a new characterisation of determinism in Measurement-Based Quantum Computing. MBQC consists in performing local measurements over a large entangled state represented by a graph. The ability to perform an overall deterministic computation requires a correction strategy because of the non-determinism of each measurement. The existence of such correction strategy depends on the underlying open graph, which is a description of the resource state together with the basis of the performed measurements. GFlow is a well-known graphical characterisation of robust determinism in MBQC when every measurement is performed in some specific planes of the Bloch sphere. While Pauli measurements are ubiquitous in MBQC, GFlow fails to be necessary for determinism when a measurement-based quantum computation involves Pauli measurements. As a consequence, Pauli Flow was designed as a generalisation of GFlow to handle MBQC with Pauli measurements: Pauli flow guarantees robust determinism, however it has been shown more recently that it fails to be a necessary condition. Our contribution is twofold. First, we demonstrate that Pauli flow is actually necessary for robust determinism in a weaker sense: given an open graph, i.e. a resource state, a deterministic computation can be driven if only if it has a Pauli flow. However, the Pauli flows do not reflect all the possible correction strategies over a particular resource state, and properties like measurement order or computational depth are not necessarily reflected by a Pauli flow. Thus, to characterise determinism in full generality, we introduce a further extension called Shadow Pauli Flow that we prove necessary and sufficient for robust determinism: An MBQC is robustly deterministic if and only if its correction strategy is consistent with a Shadow Pauli flow. Furthermore, we show that Shadow Pauli flow can be computed in polynomial time.

Related papers

• An algebraic interpretation of Pauli flow, leading to faster flow-finding algorithms [1.4732811715354455]
  We show that Pauli flow exists if and only if there is a right inverse $C$ of $M$ such that the product $NC forms the adjacency matrix of a directed acyclic graph. We obtain $mathcalO(n3)$ algorithms for finding Pauli flow, improving on the previous $mathcalO(n4)$ bound for finding generalised flow.
  arXiv  Detail & Related papers  (2024-10-30T20:30:01Z)
• Pauli Flow on Open Graphs with Unknown Measurement Labels [0.0]
  One-way quantum computation, or measurement-based quantum computation, is a universal model of quantum computation alternative to the circuit model. It is known how to efficiently determine the existence of Pauli flow given an open graph together with a measurement labelling. We show that, in the case of X and Z measurements only, flow existence corresponds to the right-invertibility of a matrix derived from the adjacency matrix.
  arXiv  Detail & Related papers  (2024-08-12T11:19:27Z)
• Robust and efficient verification of graph states in blind measurement-based quantum computation [52.70359447203418]
  Blind quantum computation (BQC) is a secure quantum computation method that protects the privacy of clients. It is crucial to verify whether the resource graph states are accurately prepared in the adversarial scenario. Here, we propose a robust and efficient protocol for verifying arbitrary graph states with any prime local dimension.
  arXiv  Detail & Related papers  (2023-05-18T06:24:45Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• Compilation of algorithm-specific graph states for quantum circuits [55.90903601048249]
  We present a quantum circuit compiler that prepares an algorithm-specific graph state from quantum circuits described in high level languages. The computation can then be implemented using a series of non-Pauli measurements on this graph state.
  arXiv  Detail & Related papers  (2022-09-15T14:52:31Z)
• Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddings [97.12538243736705]
  We study reinforcement learning with function approximation for large-scale Partially Observable Decision Processes (POMDPs) Our algorithm provably scales to large-scale POMDPs.
  arXiv  Detail & Related papers  (2022-06-24T05:13:35Z)
• Complete Flow-Preserving Rewrite Rules for MBQC Patterns with Pauli Measurements [0.0]
  We show that introducing new Z-measured qubits, connected to any subset of the existing qubits, preserves the existence of Pauli flow. We prove that any MBQC-like stabilizer ZX-diagram with Pauli flow can be rewritten into this canonical form.
  arXiv  Detail & Related papers  (2022-05-04T11:42:20Z)
• GFlowNet Foundations [66.69854262276391]
  Generative Flow Networks (GFlowNets) have been introduced as a method to sample a diverse set of candidates in an active learning context. We show a number of additional theoretical properties of GFlowNets.
  arXiv  Detail & Related papers  (2021-11-17T17:59:54Z)
• Outcome determinism in measurement-based quantum computation with qudits [0.0]
  In measurement-based quantum computing, computation is carried out by a sequence of measurements and corrections on an entangled state. We introduce flow-based methods for MBQC with qudit graph states, which we call Zd-flow, when the local dimension is an odd prime. Our main results are that Zd-flow is a necessary and sufficient condition for a strong form of outcome determinism.
  arXiv  Detail & Related papers  (2021-09-28T15:36:36Z)
• Relating Measurement Patterns to Circuits via Pauli Flow [0.0]
  We show that Pauli flow can be efficiently identified and transformed into a gate-based quantum circuit. We then use this relationship to derive simulation results for the effects of graph-theoretic rewrites in the ZX-calculus.
  arXiv  Detail & Related papers  (2021-09-13T00:48:24Z)
• Doubly Robust Off-Policy Value and Gradient Estimation for Deterministic Policies [80.42316902296832]
  We study the estimation of policy value and gradient of a deterministic policy from off-policy data when actions are continuous. In this setting, standard importance sampling and doubly robust estimators for policy value and gradient fail because the density ratio does not exist. We propose several new doubly robust estimators based on different kernelization approaches.
  arXiv  Detail & Related papers  (2020-06-06T15:52:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.