Quantum algorithm for Clifford multiplication

• URL: http://arxiv.org/abs/2607.10473v1
• Date: Sat, 11 Jul 2026 20:38:19 GMT
• Title: Quantum algorithm for Clifford multiplication
• Abstract summary: I show that a quantum computer executes the geometric product in $O(operatornamepolylog N)$ time, using logarithmic space with sublogarithmic circuit depth.<n>This exponential speedup establishes Clifford multiplication as a quantum primitive, providing an efficient computational foundation for quantum geometric algorithms and relativistic simulations.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given two dense multivectors of the Clifford algebra $C\ell(V, Q)$ with $N=2^{p+q}$ coefficients, the fastest known classical algorithms compute their geometric product in $O(N^{ω/2})$ arithmetic operations, where $ω$ denotes the matrix multiplication exponent. I show that, under amplitude encoding, a quantum computer executes the geometric product in $O(\operatorname{polylog} N)$ time, using logarithmic space with sublogarithmic circuit depth. This exponential speedup establishes Clifford multiplication as a quantum primitive, providing an efficient computational foundation for quantum geometric algorithms and relativistic simulations.

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)
• A Polylogarithmic-Depth Quantum Multiplier [0.0]
  We present a quantum algorithm for multiplying two $n$-bit integers with overall circuit depth and $T$-depth.<n>Our construction generates partial products via indicator-controlled copying and adds them using a binary adder tree.
  arXiv  Detail & Related papers  (2026-04-10T19:21:07Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Quantum Krylov Algorithm for Szegö Quadrature [0.8158532237212478]
  We present a quantum algorithm to evaluate matrix elements of functions of unitary operators.<n>The method is based on calculating quadrature nodes and weights using data collected from a quantum processor.
  arXiv  Detail & Related papers  (2025-09-23T16:13:08Z)
• Quantum oracles for the finite element method [45.200826131319815]
  This study examines the quantum routines required for the implementation of oracles used in the block-encoding of the $N times N stiffness and mass matrices.<n>We show how to construct the necessary oracles, which require the calculation of element geometry, square root and the implementation of conditional operations.
  arXiv  Detail & Related papers  (2025-04-28T14:28:31Z)
• Quantum algorithm for the gradient of a logarithm-determinant [0.0]
  The inverse of a sparse-rank input operator may be determined efficiently.<n>The algorithm is envisioned for fully error-corrected quantum computers.<n>We discuss how this algorithm can be used for kernel-based quantum machine-learning.
  arXiv  Detail & Related papers  (2025-01-16T09:39:31Z)
• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
  We propose a quantum algorithm inspired by the classical multi-row iteration method. Our algorithm places less demand on the coefficient matrix, making it suitable for solving inconsistent systems.
  arXiv  Detail & Related papers  (2024-09-06T03:32:02Z)
• A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix [2.7050250604223693]
  Finding a good approximation of the top eigenvector of a given $dtimes d$ matrix $A$ is a basic and important computational problem. We give two different quantum algorithms that output a classical description of a good approximation of the top eigenvector.
  arXiv  Detail & Related papers  (2024-05-23T16:33:13Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  We propose quantum algorithms, purely quantum in nature, for calculating the determinant and inverse of an $(N-1)times (N-1)$ matrix.<n>The basic idea is to encode each row of the matrix into a pure state of some quantum system.
  arXiv  Detail & Related papers  (2024-01-29T23:23:27Z)
• Do you know what q-means? [42.96240569413475]
  We present a classical $varepsilon$-$k$-means algorithm that performs an approximate version of one iteration of Lloyd's algorithm with time complexity.<n>We also propose an improved $q$-means quantum algorithm with time complexity.
  arXiv  Detail & Related papers  (2023-08-18T17:52:12Z)
• 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)

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.