Combinatorial necessary conditions for regular graphs to induce periodic quantum walks

• URL: http://arxiv.org/abs/2106.00166v2
• Date: Wed, 7 Jun 2023 05:07:25 GMT
• Title: Combinatorial necessary conditions for regular graphs to induce periodic quantum walks
• Abstract summary: We derive necessary conditions for discrete-time quantum walks defined by regular mixed graphs to be periodic. As an application of this work, we determine periodicity of mixed complete graphs and mixed mixed graphs with a prime number of integers.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We derive combinatorial necessary conditions for discrete-time quantum walks defined by regular mixed graphs to be periodic. If the quantum walk is periodic, all the eigenvalues of the time evolution matrices must be algebraic integers. Focusing on this, we explore which ring the coefficients of the characteristic polynomials should belong to. On the other hand, the coefficients of the characteristic polynomials of $\eta$-Hermitian adjacency matrices have combinatorial implications. From these, we can find combinatorial implications in the coefficients of the characteristic polynomials of the time evolution matrices, and thus derive combinatorial necessary conditions for mixed graphs to be periodic. For example, if a $k$-regular mixed graph with $n$ vertices is periodic, then $2n/k$ must be an integer. As an application of this work, we determine periodicity of mixed complete graphs and mixed graphs with a prime number of vertices.

Related papers

• Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
  Matrix chain multiplication is a problem in scientific computing, machine learning, and graph analysis.<n>We present emphTwo-Tower Matrix, a quantum subroutine that encodes the product $mathcalW$ of the $K$ matrices into a quantum state in circuit depth.
  arXiv  Detail & Related papers  (2026-07-14T18:42:40Z)
• Constant-Time Quantum Search with a Many-Body Quantum System [39.58317527488534]
  We consider a many-body quantum system that naturally effects parallel queries. We show that its parameters can be tuned to search a database in constant time.
  arXiv  Detail & Related papers  (2024-08-09T22:57:59Z)
• The Complexity of Envy-Free Graph Cutting [44.58084909019557]
  We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspond to the edges of a connected graph, and every agent must be assigned a connected piece of this graph. The problem is NP-complete, and we analyze its complexity with respect to two natural complexity measures: the number of agents and the number of edges in the graph.
  arXiv  Detail & Related papers  (2023-12-12T07:54:30Z)
• General Graph Random Features [42.75616308187867]
  We propose a novel random walk-based algorithm for unbiased estimation of arbitrary functions of a weighted adjacency matrix. Our algorithm enjoys subquadratic time complexity with respect to the number of nodes, overcoming the notoriously prohibitive cubic scaling of exact graph kernel evaluation.
  arXiv  Detail & Related papers  (2023-10-07T15:47:31Z)
• 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)
• Periodic Graph Transformers for Crystal Material Property Prediction [39.01618096831294]
  We consider representation learning on periodic graphs encoding crystal materials. Different from regular graphs, periodic graphs consist of a minimum unit cell repeating itself on a regular lattice in 3D space. We propose a transformer architecture, known as Matformer, for periodic graph representation learning.
  arXiv  Detail & Related papers  (2022-09-23T18:57:22Z)
• Irrational quantum walks [0.0]
  We develop theory to study any quantum walk generated by an integral Hamiltonian. We use our methods to study geometric properties of beautiful curves arising from entries of the quantum walk matrix.
  arXiv  Detail & Related papers  (2022-08-18T17:21:47Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• 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)
• Periodicity of quantum walks defined by mixed paths and mixed cycles [0.0]
  We show periodicity of quantum walks defined by mixed paths and mixed cycles. We provide a necessary and sufficient condition for a mixed cycle to be periodic and determine their periods.
  arXiv  Detail & Related papers  (2021-04-17T02:42:30Z)
• 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)
• Quantum mechanics of bipartite ribbon graphs: Integrality, Lattices and Kronecker coefficients [0.0]
  We define solvable quantum mechanical systems on a Hilbert space spanned by bipartite ribbon graphs with a fixed number of edges. The square of the Kronecker coefficient for a triple of Young diagrams is shown to be equal to the dimension of a sub-lattice in the lattice of ribbon graphs. As an avenue to explore quantum supremacy and its implications for computational complexity theory, we outline experiments to detect non-vanishing Kronecker coefficients for hypothetical quantum realizations/simulations of these quantum systems.
  arXiv  Detail & Related papers  (2020-10-08T15:18:46Z)
• Graph Gamma Process Generalized Linear Dynamical Systems [60.467040479276704]
  We introduce graph gamma process (GGP) linear dynamical systems to model real multivariate time series. For temporal pattern discovery, the latent representation under the model is used to decompose the time series into a parsimonious set of multivariate sub-sequences. We use the generated random graph, whose number of nonzero-degree nodes is finite, to define both the sparsity pattern and dimension of the latent state transition matrix.
  arXiv  Detail & Related papers  (2020-07-25T04:16:34Z)
• Can graph properties have exponential quantum speedup? [5.101801159418223]
  In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties. We show that the answer to this question depends strongly on the input model.
  arXiv  Detail & Related papers  (2020-01-28T18:45:48Z)
• Approximate Graph Spectral Decomposition with the Variational Quantum Eigensolver [1.0152838128195465]
  Spectral graph theory studies the relationships between the eigenvectors and eigenvalues of Laplacian and adjacency matrices and their associated graphs. The Variational Quantum Eigensolver (VQE) algorithm was proposed as a hybrid quantum/classical algorithm. In this paper, we will expand upon the VQE algorithm to analyze the spectra of directed and undirected graphs.
  arXiv  Detail & Related papers  (2019-12-27T23:27:38Z)

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.