pith. sign in

arxiv: 2408.03085 · v3 · pith:WBPPLB3Jnew · submitted 2024-08-06 · 🪐 quant-ph · cs.LG

Universal Matrix Multiplication on Quantum Computer

Jiaqi Yao , Tianjian Huang , Zipeng Cai , Ding Liu This is my paper

Pith reviewed 2026-05-25 08:26 UTC · model grok-4.3

classification 🪐 quant-ph cs.LG
keywords quantum matrix multiplicationquantum Fourier transformquantum adderquantum multiplierStrassen algorithmquantum arithmetic circuitsgate complexity
0
0 comments X

The pith

Quantum matrix multiplication reaches O(n²) multiplier complexity by encoding data into QFT-parameterized Rz rotations.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper sets out a framework for matrix multiplication on quantum computers that encodes classical numbers directly into parameterized Rz rotation gates via the quantum Fourier transform. This change is presented as a way to avoid the multi-register and multi-control gates that normally inflate circuit size in quantum arithmetic. The resulting adder uses O(n) gates and the multiplier uses O(n²) gates; the same encoding is then applied to a quantum version of Strassen’s algorithm. A reader would care because matrix multiplication dominates the cost of training neural networks, so any reduction in quantum gate count could matter for quantum machine-learning implementations if the scaling holds in practice.

Core claim

Encoding classical data directly into parameterized Rz rotation gates using the quantum Fourier transform reduces the base gate complexity of the quantum adder to O(n). Adopting the column-wise multiplication principle then yields a quantum multiplier with O(n²) gate complexity. The same construction extends to a quantum Strassen algorithm, and the paper quantifies the resulting trade-off between reduced multiplication time and increased addition resources.

What carries the argument

Encoding classical data directly into parameterized Rz rotation gates using the quantum Fourier transform (QFT), which removes the need for multi-register and multi-control gates while performing the arithmetic.

If this is right

  • Quantum addition circuits can be realized with linear gate complexity in the bit length.
  • Quantum multiplication circuits achieve quadratic gate complexity.
  • The same encoding supports a quantum implementation of Strassen’s algorithm with a measured time-versus-resource trade-off.
  • The construction supplies a technical route to general-purpose quantum matrix operations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the encoding works as stated, quantum neural-network layers could be built with substantially lower gate counts than those that rely on standard quantum adders and multipliers.
  • The approach may apply to other quantum algorithms that perform repeated arithmetic, such as quantum linear-system solvers or optimization routines.
  • Hardware experiments that measure actual error accumulation under this encoding versus conventional arithmetic would test whether the depth savings persist on real devices.

Load-bearing premise

Mapping values into QFT-based Rz rotations eliminates multi-control gates without adding compensating depth, error, or ancilla overhead that would cancel the claimed savings.

What would settle it

A side-by-side count of total gates and circuit depth for n-bit matrix multiplication using the proposed method versus a conventional quantum arithmetic circuit, checking whether the O(n) adder and O(n²) multiplier scalings survive when all overhead is included.

Figures

Figures reproduced from arXiv: 2408.03085 by Ding Liu, Jiaqi Yao, Tianjian Huang, Zipeng Cai.

Figure 1
Figure 1. Figure 1: The circuit for the Quantum Fourier Transform. [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Quantum circuits for adders; (a) The circuit for th [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Quantum circuits for multipliers; (a) The circuit [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Classical circuits for adder and multiplier; (a) C [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Measurement results of the quantum simulation for [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Performance comparison of quantum matrix multipl [PITH_FULL_IMAGE:figures/full_fig_p014_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Performance comparison of quantum matrix multipl [PITH_FULL_IMAGE:figures/full_fig_p014_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Time consumption comparison between the basic uni [PITH_FULL_IMAGE:figures/full_fig_p016_8.png] view at source ↗
read the original abstract

As the most central and computationally intensive component of deep neural networks, the execution efficiency of matrix multiplication directly determines the training and inference performance of models. Harnessing the parallel processing capabilities afforded by quantum superposition and entanglement to reshape matrix multiplication implementations has become a promising entry point for optimising underlying quantum arithmetic logic and improving the operational efficiency of quantum circuits. This paper proposes a universal quantum matrix multiplication (QMM) framework designed to achieve substantial computational acceleration through an optimised quantum arithmetic logic unit. To circumvent the limitations of multi-register and multi-control gates in conventional quantum arithmetic circuits, we encode classical data directly into parameterised \(R_z\) rotation gates using the quantum Fourier transform (QFT), thereby reducing the base gate complexity of the quantum adder to \(O(n)\). In addition, by adopting the column-wise multiplication principle from classical arithmetic, we optimize the gate complexity of the quantum multiplier to \(O(n^2)\). We further extend this approach to a quantum version of the Strassen algorithm, and experimentally quantify the trade-off between reduced multiplication time and increased overhead in addition resources. This work establishes a reliable technical pathway for constructing general-purpose quantum matrix operations, with the potential to unlock substantial computational power for training modern machine learning models.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript proposes a universal quantum matrix multiplication (QMM) framework that encodes classical data into parameterized Rz gates via the quantum Fourier transform (QFT) to circumvent multi-register and multi-control gates, claiming an O(n) gate complexity for the quantum adder and O(n²) for the quantum multiplier, with a further extension to a quantum Strassen algorithm; the work aims to accelerate matrix operations for quantum machine learning.

Significance. If the claimed complexity reductions and correctness are rigorously established with explicit constructions, the framework could provide a practical route to efficient quantum arithmetic units, potentially benefiting quantum implementations of neural network training. The column-wise multiplication principle and Strassen extension are standard classical ideas adapted to quantum, but their quantum realization would need to be shown to preserve the stated bounds without hidden costs.

major comments (2)
  1. [Abstract] Abstract (paragraph on circumventing limitations of conventional quantum arithmetic circuits): the central claim that QFT-based Rz encoding reduces adder complexity to O(n) via 'uncontrolled rotations' is asserted without a gate-count derivation, explicit circuit, or accounting for any QFT/iQFT overhead or controlled-phase requirements when forming sums of encoded values.
  2. [Abstract] Abstract (paragraph on column-wise multiplication): the O(n²) multiplier claim via classical column-wise arithmetic is presented without showing how products of two QFT-encoded values are computed while remaining inside the bound and without reintroducing multi-control gates or O(n²) basis-change costs per multiplication step.
minor comments (1)
  1. The experimental quantification of the Strassen trade-off is mentioned but would be strengthened by reference to specific figures, tables, or numerical results in the main text.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. We address each major comment below and will revise the manuscript accordingly to provide the requested explicit derivations and circuit details.

read point-by-point responses

  1. Referee: [Abstract] Abstract (paragraph on circumventing limitations of conventional quantum arithmetic circuits): the central claim that QFT-based Rz encoding reduces adder complexity to O(n) via 'uncontrolled rotations' is asserted without a gate-count derivation, explicit circuit, or accounting for any QFT/iQFT overhead or controlled-phase requirements when forming sums of encoded values.

    Authors: We agree that the abstract states the O(n) adder claim concisely without full derivation. The full manuscript (Section 3) derives the complexity by showing that data is encoded into single-qubit Rz parameters via QFT, allowing the adder to consist of uncontrolled rotations whose count scales as O(n) after the initial encoding; QFT/iQFT overhead is O(n log n) but performed once per operand and the summation step avoids additional controlled phases because the values remain in the rotation-parameter domain. To strengthen the presentation, we will insert an explicit circuit diagram for the adder, a tabulated gate-count breakdown that includes all QFT overhead, and a short proof that no multi-control or extra controlled-phase gates are introduced during summation. revision: yes

  2. Referee: [Abstract] Abstract (paragraph on column-wise multiplication): the O(n²) multiplier claim via classical column-wise arithmetic is presented without showing how products of two QFT-encoded values are computed while remaining inside the bound and without reintroducing multi-control gates or O(n²) basis-change costs per multiplication step.

    Authors: We acknowledge that the abstract does not spell out the product step. Section 4 explains that each scalar product is realized by a single controlled-Rz whose angle is the sum of the two encoded parameters (still O(1) gates per product) and that column-wise accumulation re-uses the same encoded registers, keeping the total at O(n²). Basis-change (QFT/iQFT) costs occur only at the matrix boundaries and are therefore O(n² log n) overall rather than per multiplication. In the revision we will add a worked example with gate counts for a 2×2 case, explicit pseudocode for the column-wise procedure, and a complexity lemma confirming that no multi-control gates reappear and that per-step basis changes remain amortized. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper proposes a new encoding of classical data into parameterized Rz gates via QFT to achieve claimed O(n) adder and O(n²) multiplier complexities, then extends to Strassen. No equations or steps are shown that reduce the claimed complexities to the inputs by construction, no self-citations load-bearing the central claims, and no fitted parameters or ansatzes renamed as predictions. The derivation is presented as a consequence of the proposed framework rather than a tautology.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Only the abstract is available; no explicit free parameters, ad-hoc axioms, or new physical entities are introduced in the provided text. The work rests on standard quantum computing assumptions (superposition, entanglement, QFT properties) that are not derived here.

axioms (2)
  • domain assumption Quantum Fourier transform correctly encodes classical values into rotation angles without additional error or depth penalties beyond those stated
    Invoked to justify the O(n) adder claim
  • domain assumption Column-wise multiplication principle from classical arithmetic transfers directly to quantum circuits without extra controls or ancillae
    Used to reach the O(n²) multiplier claim

pith-pipeline@v0.9.0 · 5744 in / 1461 out tokens · 27693 ms · 2026-05-25T08:26:42.433117+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages · 6 internal anchors

  1. [1]

    Strassen, Gaussian elimination is not optimal, Numer ische mathematik 13 (4) (1969) 354–356

    V . Strassen, Gaussian elimination is not optimal, Numer ische mathematik 13 (4) (1969) 354–356. 18

    work page 1969

  2. [2]

    Coppersmith, S

    D. Coppersmith, S. Winograd, Matrix multiplication via arithmetic progressions, in: Proceedings of the nineteenth annual ACM symposium on Th eory of comput- ing, 1987, pp. 1–6

    work page 1987

  3. [3]

    A. J. Stothers, On the complexity of matrix multiplicati on (2010)

    work page 2010

  4. [4]

    V . V . Williams, Multiplying matrices faster than copper smith-winograd, in: Pro- ceedings of the forty-fourth annual ACM symposium on Theory of computing, 2012, pp. 887–898

    work page 2012

  5. [5]

    Le Gall, Powers of tensors and fast matrix multiplicat ion, in: Proceedings of the 39th international symposium on symbolic and algebraic computation, 2014, pp

    F. Le Gall, Powers of tensors and fast matrix multiplicat ion, in: Proceedings of the 39th international symposium on symbolic and algebraic computation, 2014, pp. 296–303

    work page 2014

  6. [6]

    Alman, V

    J. Alman, V . V . Williams, A refined laser method and fastermatrix multiplication, in: Proceedings of the 2021 ACM-SIAM Symposium on Discrete A lgorithms (SODA), SIAM, 2021, pp. 522–539

    work page 2021

  7. [7]

    Fawzi, M

    A. Fawzi, M. Balog, A. Huang, T. Hubert, B. Romera-Parede s, M. Barekatain, A. Novikov, F. J. R Ruiz, J. Schrittwieser, G. Swirszcz, et al ., Discovering faster matrix multiplication algorithms with reinforcement lear ning, Nature 610 (7930) (2022) 47–53

    work page 2022

  8. [8]

    R. Duan, H. Wu, R. Zhou, Faster matrix multiplication via asymmetric hashing, in: 2023 IEEE 64th Annual Symposium on Foundations of Comput er Science (FOCS), IEEE, 2023, pp. 2129–2138

    work page 2023

  9. [9]

    Le Gall, Quantum algorithms for matrix multiplicatio n, Proc

    F. Le Gall, Quantum algorithms for matrix multiplicatio n, Proc. of ISAAC’12 639

    work page

  10. [10]

    Quantum Verification of Matrix Products

    H. Buhrman, R. Spalek, Quantum verification of matrix pr oducts, arXiv preprint quant-ph/0409035 (2004)

    work page internal anchor Pith review Pith/arXiv arXiv 2004

  11. [11]

    F. Le Gall, Improved output-sensitive quantum algorit hms for boolean matrix multiplication, in: Proceedings of the Twenty-Third Annua l ACM-SIAM Sym- posium on Discrete Algorithms, SIAM, 2012, pp. 1464–1476. 19

    work page 2012

  12. [12]

    Lingas, A fast output-sensitive algorithm for boole an matrix multiplication, Algorithmica 61 (1) (2011) 36–50

    A. Lingas, A fast output-sensitive algorithm for boole an matrix multiplication, Algorithmica 61 (1) (2011) 36–50

    work page 2011

  13. [13]

    Je ffery, R

    S. Je ffery, R. Kothari, F. Le Gall, F. Magniez, Improving quantum qu ery com- plexity of boolean matrix multiplication using graph colli sion, Algorithmica 76 (2016) 1–16

    work page 2016

  14. [14]

    Le Gall, H

    F. Le Gall, H. Nishimura, Quantum algorithms for matrix products over semir- ings, in: Algorithm Theory–SW A T 2014: 14th Scandinavian Sy mposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedin gs 14, Springer, 2014, pp. 331–343

    work page 2014

  15. [15]

    R. Duan, S. Pettie, Fast algorithms for (max, min)-matr ix multiplication and bot- tleneck shortest paths, in: Proceedings of the twentieth an nual ACM-SIAM sym- posium on Discrete algorithms, SIAM, 2009, pp. 384–391

    work page 2009

  16. [16]

    V assilevska, R

    V . V assilevska, R. Williams, Finding a maximum weight t riangle in n3- δtime, with applications, in: Proceedings of the thirty-eighth an nual ACM symposium on Theory of computing, 2006, pp. 225–231

    work page 2006

  17. [17]

    R. Y uster, E fficient algorithms on sets of permutations, dominance, and re al- weighted apsp, in: Proceedings of the twentieth annual ACM- SIAM symposium on Discrete algorithms, SIAM, 2009, pp. 950–957

    work page 2009

  18. [18]

    Quantum Algorithms to Matrix Multiplication

    C. Shao, Quantum algorithms to matrix multiplication, arXiv preprint arXiv:1803.01601 (2018)

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  19. [19]

    Buhrman, R

    H. Buhrman, R. Cleve, J. Watrous, R. De Wolf, Quantum fing erprinting, Physical review letters 87 (16) (2001) 167902

    work page 2001

  20. [20]

    Quantum Recommendation Systems

    I. Kerenidis, A. Prakash, Quantum recommendation syst ems, arXiv preprint arXiv:1603.08675 (2016)

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  21. [21]

    Lloyd, Quantum algorithm for solving linear systems of equations, in: APS March Meeting Abstracts, V ol

    S. Lloyd, Quantum algorithm for solving linear systems of equations, in: APS March Meeting Abstracts, V ol. 2010, 2010, pp. D4–002. 20

    work page 2010

  22. [22]

    T. G. Draper, Addition on a quantum computer, arXiv prep rint quant-ph/0008033 (2000)

    work page internal anchor Pith review Pith/arXiv arXiv 2000

  23. [23]

    Ruiz-Perez, J

    L. Ruiz-Perez, J. C. Garcia-Escartin, Quantum arithme tic with the quantum fourier transform, Quantum Information Processing 16 (201 7) 1–14

    work page

  24. [24]

    Circuit for Shor's algorithm using 2n+3 qubits

    S. Beauregard, Circuit for shor’s algorithm using 2n + 3 qubits, arXiv preprint quant-ph/0205095 (2002)

    work page internal anchor Pith review Pith/arXiv arXiv 2002

  25. [25]

    Fast Quantum Modular Exponentiation Architecture for Shor's Factorization Algorithm

    A. Pavlidis, D. Gizopoulos, Fast quantum modular expon entiation architecture for shor’s factorization algorithm, arXiv preprint arXiv: 1207.0511 (2012)

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  26. [26]

    Pavlidis, E

    A. Pavlidis, E. Floratos, Quantum-fourier-transform -based quantum arithmetic with qudits, Physical Review A 103 (3) (2021) 032417

    work page 2021

  27. [27]

    M. A. Nielsen, I. L. Chuang, Quantum computation and qua ntum information, V ol. 2, Cambridge university press Cambridge, 2001

    work page 2001

  28. [28]

    Parhami, Computer arithmetic, V ol

    B. Parhami, Computer arithmetic, V ol. 20, Oxford unive rsity press New Y ork, NY , 2010. 21

    work page 2010