Exact recursive calculation of circulant permanents: A band of different diagonals inside a uniform matrix

• URL: http://arxiv.org/abs/2109.01740v1
• Date: Fri, 3 Sep 2021 21:56:14 GMT
• Title: Exact recursive calculation of circulant permanents: A band of different diagonals inside a uniform matrix
• Authors: Vitaly V. Kocharovsky, Vladimir V. Kocharovsky, Vladimir Yu. Martyanov, Sergey V. Tarasov
• Abstract summary: The proposed system of linear recurrence equations with variable coefficients provides a powerful tool for the analysis of the circulants. Its solution would be tremendously important for a unified analysis of a wide range of the nature's #P-hard problems.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a finite-order system of recurrence relations for a permanent of circulant matrices containing a band of k any-value diagonals on top of a uniform matrix (for k = 1, 2, and 3) as well as the method for deriving such recurrence relations which is based on the permanents of the matrices with defects. The proposed system of linear recurrence equations with variable coefficients provides a powerful tool for the analysis of the circulant permanents, their fast, linear time computing and finding their asymptotics in a large-matrix-size limit. The latter problem is an open fundamental problem. Its solution would be tremendously important for a unified analysis of a wide range of the nature's #P-hard problems, including problems in the physics of many-body systems, critical phenomena, quantum computing, quantum field theory, theory of chaos, fractals, theory of graphs, number theory, combinatorics, cryptography, etc.

Related papers

• Solving the Nonlinear Vlasov Equation on a Quantum Computer [0.0]
  We present a mapping of the nonlinear, electrostatic Vlasov equation with Krook type collision operators, discretized on a (1 + 1) dimensional grid. We show that the quantum algorithm is guaranteed to converge only when the plasma parameters take unphysical values.
  arXiv  Detail & Related papers  (2024-11-28T18:32:30Z)
• Eigenstate Correlations in Dual-Unitary Quantum Circuits: Partial Spectral Form Factor [0.0]
  Analytic insights into eigenstate correlations can be obtained by the recently introduced partial spectral form factor. We study the partial spectral form factor in chaotic dual-unitary quantum circuits in the thermodynamic limit.
  arXiv  Detail & Related papers  (2024-07-29T12:02:24Z)
• Positive Moments Forever: Undecidable and Decidable Cases [1.3124513975412255]
  We show that the positivity problem for simple unitary linear recurrence sequences is decidable, and is undecidable for linear recurrence sequences over the ring of commutatives. As a byproduct, we prove a free version of Polya's theorem.
  arXiv  Detail & Related papers  (2024-04-23T13:53:37Z)
• Polynomial-time Solver of Tridiagonal QUBO and QUDO problems with Tensor Networks [41.94295877935867]
  We present an algorithm for solving tridiagonal Quadratic Unconstrained Binary Optimization (QUBO) problems and Quadratic Unconstrained Discrete Optimization (QUDO) problems with one-neighbor interactions. Our method is based on the simulation of a quantum state to which we will apply an imaginary time evolution and perform a series of partial traces to obtain the state of maximum amplitude.
  arXiv  Detail & Related papers  (2023-09-19T10:45:15Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• Identifiability and Asymptotics in Learning Homogeneous Linear ODE Systems from Discrete Observations [114.17826109037048]
  Ordinary Differential Equations (ODEs) have recently gained a lot of attention in machine learning. theoretical aspects, e.g., identifiability and properties of statistical estimation are still obscure. This paper derives a sufficient condition for the identifiability of homogeneous linear ODE systems from a sequence of equally-spaced error-free observations sampled from a single trajectory.
  arXiv  Detail & Related papers  (2022-10-12T06:46:38Z)
• Identifiability in Exact Two-Layer Sparse Matrix Factorization [0.0]
  Sparse matrix factorization is the problem of approximating a matrix Z by a product of L sparse factors X(L) X(L--1). This paper focuses on identifiability issues that appear in this problem, in view of better understanding under which sparsity constraints the problem is well-posed.
  arXiv  Detail & Related papers  (2021-10-04T07:56:37Z)
• The Transfer Matrix Method and The Theory of Finite Periodic Systems. From Heterostructures to Superlattices [0.0]
  Long-period systems and superlattices have new effects on the energy spectrum and wave functions. Most approaches adjust theories for infinite systems, which is acceptable for small number of unit cells $n$. We review some applications of the transfer-matrix method with Floquet's theorem to negative resistance, ballistic transistors, channel coupling, spintronics, superluminal, and optical antimatter effects.
  arXiv  Detail & Related papers  (2021-09-23T20:45:29Z)
• Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time [46.31710224483631]
  We show how to bypass the main open question of Nelson and Nguyen (FOCS, 2013) regarding the logarithmic factors in the sketching dimension for existing constant factor approximation oblivious subspace embeddings. A key technique we use is an explicit mapping of Indyk based on uncertainty principles and extractors. For the fundamental problems of rank computation and finding a linearly independent subset of columns, our algorithms improve Cheung, Kwok, and Lau (JACM, 2013) and are optimal to within a constant factor and a $loglog(n)$-factor, respectively.
  arXiv  Detail & Related papers  (2021-07-16T19:34:10Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data. We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
  arXiv  Detail & Related papers  (2020-06-16T21:56:22Z)

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.