An algebraic interpretation of Pauli flow, leading to faster flow-finding algorithms

• URL: http://arxiv.org/abs/2410.23439v1
• Date: Wed, 30 Oct 2024 20:30:01 GMT
• Title: An algebraic interpretation of Pauli flow, leading to faster flow-finding algorithms
• Authors: Piotr Mitosek, Miriam Backens,
• Abstract summary: 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.
• Score: 1.4732811715354455
• License:
• Abstract: The one-way model of quantum computation is an alternative to the circuit model. A one-way computation is driven entirely by successive adaptive measurements of a pre-prepared entangled resource state. For each measurement, only one outcome is desired; hence a fundamental question is whether some intended measurement scheme can be performed in a robustly deterministic way. So-called flow structures witness robust determinism by providing instructions for correcting undesired outcomes. Pauli flow is one of the broadest of these structures and has been studied extensively. It is known how to find flow structures in polynomial time when they exist; nevertheless, their lengthy and complex definitions often hinder working with them. We simplify these definitions by providing a new algebraic interpretation of Pauli flow. This involves defining two matrices arising from the adjacency matrix of the underlying graph: the flow-demand matrix $M$ and the order-demand matrix $N$. 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. From the newly defined algebraic interpretation, we obtain $\mathcal{O}(n^3)$ algorithms for finding Pauli flow, improving on the previous $\mathcal{O}(n^4)$ bound for finding generalised flow, a weaker variant of flow, and $\mathcal{O}(n^5)$ bound for finding Pauli flow. We also introduce a first lower bound for the Pauli flow-finding problem, by linking it to the matrix invertibility and multiplication problems over $\mathbb{F}_2$.

Related papers

• Pauli Transfer Matrices [0.0]
  Pauli transfer matrices show the action of a linear map in the $n$-qubit Pauli basis. We propose new algorithms that make explicit use of the tensor product structure of the Pauli basis.
  arXiv  Detail & Related papers  (2024-11-01T11:52:51Z)
• Quantum computational complexity of matrix functions [2.7488316163114823]
  We study the computational complexity of two primitive problems. We consider four functions -- monomials, Chebyshevs, the time evolution function, and the inverse function.
  arXiv  Detail & Related papers  (2024-10-17T18:00:03Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Pauli Decomposition via the Fast Walsh-Hadamard Transform [0.0]
  We present a new exact and explicit formula for the Pauli string coefficients. We show that up to a permutation of the matrix elements, the decomposition coefficients are related to the original matrix by a multiplication of a generalised Hadamard matrix. A numerical implementation of our equation outperforms currently available solutions.
  arXiv  Detail & Related papers  (2024-08-12T14:56:45Z)
• 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)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  We propose a natural algorithm that involves imputing the missing values of the matrix $XTX$. We evaluate our algorithm on one-sided recovery of synthetic data and low-coverage genome sequencing.
  arXiv  Detail & Related papers  (2023-06-06T22:35:16Z)
• 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)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Leveraged Matrix Completion with Noise [84.20092979053119]
  We show that we can provably recover an unknown $ntimes n$ matrix of rank $r$ from just about $mathcalO(nrlog2 (n))$ entries. Our proofs are supported by a novel approach that phrases sufficient optimality conditions based on the Golfing Scheme.
  arXiv  Detail & Related papers  (2020-11-11T16:25:45Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  We show that learning $ktimes k$, rank-$r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ samples. We propose an algorithm that uses $cal O(frackrepsilon2log2fracepsilon)$ samples, a number linear in the high dimension, and nearly linear in the matrices, typically low, rank proofs.
  arXiv  Detail & Related papers  (2020-09-30T19:10:32Z)

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.