arXiv:2607.10473
Quantum algorithm for Clifford multiplication
Kagwe A. Muchane
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.
AI Summary
The paper asks whether the geometric product of two Clifford multivectors can be computed efficiently from amplitude-encoded coefficient states. For an algebra with $N=2^n$ basis blades, it expresses multiplication as cocycle-twisted convolution over $(\mathbb Z_2)^n$: $c_z=\sum_x a_xb_{x\oplus z}\chi(x,x\oplus z)$. The proposed circuit applies the cocycle phase, computes XOR between the registers, and applies a Walsh–Hadamard transform to the first register. Postselecting that register onto $0^n$ produces the normalized coefficient state of the product. The cocycle is a quadratic Boolean phase encoding generator exchanges and metric signs. A reversible binary prefix-sum construction implements its oracle using $O(n)$ two-qubit gates and depth $O(n)$; a parallel-prefix variant is stated to use $O(n\log n)$ gates and depth $O(\log n)$. These give corresponding per-attempt multiplication costs, with $O(n)$ qubits. The construction is also formulated for efficiently presented twisted group algebras. The central qualification is the success probability: for normalized inputs, $p_0=\|AB\|_2^2/N$. The paper estimates that typical random dense inputs have $p_0=O(1/N)$, so the small per-attempt circuit does not establish generic polylogarithmic-time product-state preparation. Amplitude amplification requires $O(1/\sqrt{p_0})$ iterations and efficient input-state reflections. Support-adapted projection can improve success for small supports, although sparse multiplication is also classically efficient. Arbitrary input preparation and full classical output extraction require resources scaling with $N$. Proposed applications concern product-state observables under efficient preparation and inverse-polynomial-success promises; no concrete application speedup is established.
Central claim may not hold: The abstract claims general polylogarithmic-time multiplication, but the circuit succeeds with probability ||AB||_2^2/N, which can entail exponentially many repetitions in the geometric dimension. Efficient product-state preparation requires additional success-probability and state-preparation promises that amplitude encoding alone does not provide. The advertised sublogarithmic depth applies to a single attempt rather than to successful product-state preparation with bounded failure probability. The exponential-speedup claim compares classical full-array computation with conditional quantum-state preparation without establishing an exponential advantage for a matched computational task.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 21 pages, 4 figures, 3 tables