Quantum algorithms for equational reasoning

• URL: http://arxiv.org/abs/2508.21122v1
• Date: Thu, 28 Aug 2025 18:00:06 GMT
• Title: Quantum algorithms for equational reasoning
• Authors: Davide Rattacaso, Daniel Jaschke, Marco Ballarin, Ilaria Siloi, Simone Montangero,
• Abstract summary: We introduce quantum normal form reduction, a quantum computational framework for analyzing symbolic expressions.<n>We demonstrate a quantum-inspired version of the algorithm using tensor network simulations.<n>This framework opens the path for quantum symbolic computation in areas ranging from quantum and logical circuit design to data compression.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce quantum normal form reduction, a quantum computational framework for analyzing abstract symbolic expressions - such as strings, algebraic formulas, or quantum circuits - that are equivalent under a given set of transformation rules. These rules form a term rewriting system, a formal method for deriving equivalences by repeatedly applying substitutions. We construct an efficiently implementable quantum Hamiltonian whose ground state encodes the entire class of equivalent expressions - potentially exponentially many - in a quantum superposition. By preparing and manipulating these ground states, we address fundamental problems in equational reasoning, including the word problem, i.e., determining whether two expressions are equivalent, counting the number of equivalent expressions, and identifying structural properties of equivalence classes. We demonstrate a quantum-inspired version of the algorithm using tensor network simulations by solving instances involving up to $10^{28}$ equivalent expressions, well beyond the reach of standard classical graph exploration techniques. This framework opens the path for quantum symbolic computation in areas ranging from quantum and logical circuit design to data compression, computational group theory, linguistics, polymers and biomolecular modeling, enabling the investigation of problems previously out of reach.

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Quantum Algorithms for Compositional Text Processing [1.3654846342364308]
  We focus on the recently proposed DisCoCirc framework for natural language, and propose a quantum adaptation, QDisCoCirc. This is motivated by a compositional approach to rendering AI interpretable. For the model-native primitive operation of text similarity, we derive quantum algorithms for fault-tolerant quantum computers.
  arXiv  Detail & Related papers  (2024-08-12T11:21:40Z)
• Quantum computing topological invariants of two-dimensional quantum matter [0.0]
  We present two quantum circuits for calculating Chern numbers of two-dimensional quantum matter on quantum computers.<n>First algorithm uses many qubits, and we analyze it using a tensor-network simulator of quantum circuits.<n>Second circuit uses fewer qubits, and we implement it experimentally on a quantum computer based on superconducting qubits.
  arXiv  Detail & Related papers  (2024-04-09T06:22:50Z)
• Solving reaction dynamics with quantum computing algorithms [42.408991654684876]
  We study quantum algorithms for response functions, relevant for describing different reactions governed by linear response.<n>We focus on nuclear-physics applications and consider a qubit-efficient mapping on the lattice, which can efficiently represent the large volumes required for realistic scattering simulations.
  arXiv  Detail & Related papers  (2024-03-30T00:21:46Z)
• Determining the ability for universal quantum computing: Testing controllability via dimensional expressivity [39.58317527488534]
  Controllability tests can be used in the design of quantum devices to reduce the number of external controls. We devise a hybrid quantum-classical algorithm based on a parametrized quantum circuit.
  arXiv  Detail & Related papers  (2023-08-01T15:33:41Z)
• Semantic embedding for quantum algorithms [0.0]
  A need has developed for an assurance of the correctness of high-level quantum algorithmic reasoning. Many quantum algorithms have been unified and improved using quantum signal processing (QSP) and quantum singular value transformation (QSVT) We show that QSP/QSVT can be treated and combined modularly, purely in terms of the functional transforms they embed. We also identify existing quantum algorithms whose use of semantic embedding is implicit, spanning from distributed search to soundness in quantum cryptography.
  arXiv  Detail & Related papers  (2023-04-27T17:55:40Z)
• Visualizing Quantum Circuit Probability -- estimating computational action for quantum program synthesis [0.0]
  The probability of states in the circuit model of computation is defined. The reachability and expressibility in a space-time-bounded setting for classical and quantum gate sets are enumerated and visualized. The article suggests how applications like geometric quantum machine learning, novel quantum algorithm and quantum artificial general intelligence can benefit from studying circuit probabilities.
  arXiv  Detail & Related papers  (2023-04-05T10:49:36Z)
• General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory [44.99833362998488]
  We introduce quantum algorithms that can efficiently simulate certain classes of interactions consisting of correlated changes in multiple quantum numbers. The lattice gauge theory studied is the SU(2) gauge theory in 1+1 dimensions coupled to one flavor of staggered fermions. The algorithms are shown to be applicable to higher-dimensional theories as well as to other Abelian and non-Abelian gauge theories.
  arXiv  Detail & Related papers  (2022-12-28T18:56:25Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  We propose a variational quantum algorithm for performing quantum dynamics in first quantization. Our simulations exhibit the previously observed numerical instabilities of variational time propagation approaches.
  arXiv  Detail & Related papers  (2022-03-04T19:00:45Z)
• Numerical Simulations of Noisy Quantum Circuits for Computational Chemistry [51.827942608832025]
  Near-term quantum computers can calculate the ground-state properties of small molecules. We show how the structure of the computational ansatz as well as the errors induced by device noise affect the calculation.
  arXiv  Detail & Related papers  (2021-12-31T16:33:10Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)
• Sign Problems in Quantum Field Theory: Classical and Quantum Approaches [0.0]
  lattice field computation theory provides non-perturbative access to equilibrium physics of quantum fields. When applied to certain fermionic systems, or to the calculation of out-of-equilibrium physics, Monte Carlo calculations encounter the so-called sign problem. This thesis details two methods for mitigating or avoiding the sign problem.
  arXiv  Detail & Related papers  (2020-06-05T20:57:51Z)

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.