The matrix permanent and determinant from a spin system

• URL: http://arxiv.org/abs/2307.04681v1
• Date: Mon, 10 Jul 2023 16:34:55 GMT
• Title: The matrix permanent and determinant from a spin system
• Authors: Abhijeet Alase, Owen Doty, and David L. Feder
• Abstract summary: Gauss-Jordan for the determinant of $M$ is then equivalent to the successive removal of the generalized zero eigenspace of the fermionic $breveM$. Our analysis may point the way to new strategies for classical and quantum evaluation of the permanent.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In contrast to the determinant, no algorithm is known for the exact determination of the permanent of a square matrix that runs in time polynomial in its dimension. Consequently, non interacting fermions are classically efficiently simulatable while non-interacting bosons are not, underpinning quantum supremacy arguments for sampling the output distribution of photon interferometer arrays. This work introduces a graph-theoretic framework that bridges both the determinant and permanent. The only non-zero eigenvalues of a sparse non-Hermitian operator $\breve{M}$ for $n$ spin-$1/2$ particles are the $n$th roots of the permanent or determinant of an $n\times n$ matrix $M$, interpreting basis states as bosonic or fermionic occupation states, respectively. This operator can be used to design a simple and straightforward method for the classical determination of the permanent that matches the efficiency of the best-known algorithm. Gauss-Jordan elimination for the determinant of $M$ is then equivalent to the successive removal of the generalized zero eigenspace of the fermionic $\breve{M}$, equivalent to the deletion of some nodes and reweighting of the remaining edges in the graph such that only $n$ nodes survive after the last step. In the bosonic case, the successive removal of generalized zero eigenspaces for $\breve{M}$ is also equivalent to node deletion, but new edges are added during this process, which gives rise to the higher complexity of computing the permanent. Our analysis may point the way to new strategies for classical and quantum evaluation of the permanent.

Related papers

• Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
  We consider the spectral tail condition number, $kappa_ell$, defined as the ratio between the $ell$th largest and the smallest singular value of the matrix representing the system. Some of the implications of our result, and of the use of $kappa_ell$, include direct improvement over a fine-grained analysis of the Conjugate method.
  arXiv  Detail & Related papers  (2024-05-09T14:56:49Z)
• Vectorization of the density matrix and quantum simulation of the von Neumann equation of time-dependent Hamiltonians [65.268245109828]
  We develop a general framework to linearize the von-Neumann equation rendering it in a suitable form for quantum simulations. We show that one of these linearizations of the von-Neumann equation corresponds to the standard case in which the state vector becomes the column stacked elements of the density matrix. A quantum algorithm to simulate the dynamics of the density matrix is proposed.
  arXiv  Detail & Related papers  (2023-06-14T23:08:51Z)
• Purity decay rate in random circuits with different configurations of gates [0.0]
  We study purity decay -- a measure for bipartite entanglement -- in a chain of $n$ under the action of various geometries. In most circuits, purity decays to its value in two stages: the initial thermodynamically relevant decay up to extensive times is $sim lambda_mathrmeffeff$, with $lambda_mathrmeff$ not necessarily being in the spectrum of the transfer matrix.
  arXiv  Detail & Related papers  (2022-11-24T12:32:07Z)
• Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion [28.431572772564518]
  Given a symmetric matrix $M$ and a vector $lambda$, we present new bounds on the Frobenius-distance utility of the Gaussian mechanism for approximating $M$ by a matrix. Our bounds depend on both $lambda$ and the gaps in the eigenvalues of $M$, and hold whenever the top $k+1$ eigenvalues of $M$ have sufficiently large gaps.
  arXiv  Detail & Related papers  (2022-11-11T18:54:01Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Rank-one matrix estimation: analytic time evolution of gradient descent dynamics [16.067228939231047]
  We consider a rank-one symmetric matrix corrupted by additive noise. Explicit formulas for the whole time evolution of the overlap between the estimator and unknown vector, as well as the cost, are rigorously derived.
  arXiv  Detail & Related papers  (2021-05-25T23:31:08Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Exceptional points and domains of unitarity for a class of strongly non-Hermitian real-matrix Hamiltonians [0.0]
  A Hamiltonian of a closed (i.e., unitary) quantum system is assumed to have an $N$ by $N$ real-matrix form. We describe the quantum phase-transition boundary $partial cal D[N]$ at which the unitarity of the system is lost.
  arXiv  Detail & Related papers  (2021-04-22T12:27:09Z)
• 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)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)

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.