Evaluation of the complexity of unitary matrix factorization and its analogy with the discrete logarithm problem

Bojana Tomašević Dražić[/], Miloš Dražić
Belgrade Metropolitan University, Serbia
bojana.tomasevic@metropolitan.ac.rs
milos.drazic@metropolitan.ac.rs
DOI: 10.46793/BISEC25.241TD

 
ABSTRACT: Unitary matrices play a central role in quantum computing, forming the mathematical foundation for quantum gates and transformations.

This paper investigates the computational complexity of unitary matrix factorization, a problem defined as decomposing a given unitary matrix U∈U(n) into an unknown product of smaller unitary factors  U=A_1 A_2…A_k,       A_i∈U(n)
The study draws an analogy between this problem and the classical discrete logarithm problem, extending it into the continuous domain of complex-valued unitary groups.
We present both theoretical and empirical evidence that the computational effort required for unitary matrix factorization grows approximately as O(n^3 k), where n is the matrix dimension and k the number of factors.
Empirical evaluation in Python (NumPy + QR decomposition) confirms cubic scaling with dimension and linear scaling with factor count.
Unlike integer factorization, no known quantum algorithm, such as Shor’s or HHL, efficiently solves this problem.
We discuss how the apparent hardness of this operation could form the basis of a post-quantum cryptographic primitive resistant to quantum attacks.

 

KEYWORDS: Unitary matrix factorization, computational complexity, discrete logarithm problem, quantum cryptography

REFERENCES:

  1. P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, pp. 124–134, (1994).
  2. A. W. Harrow, A. Hassidim, S. Lloyd, Quantum algorithm for linear systems of equations, Physical Review Letters 103 (15), pp. 150502, (2009).
  3. V. Strassen, Gaussian elimination is not optimal, Numerische Mathematik 13 (4), pp. 354–356, (1969).
  4. D. Coppersmith, S. Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation 9 (3), pp. 251–280, (1990).
  5. E. K. P. Chong, W. S. Lu, S. H. Zak, An Introduction to Optimization, 5th edn. John Wiley & Sons, Inc., Hoboken, New Jersey, (2024).
  6. J. Hromkovič, Algorithmics for Hard Problems, 2nd edn. Springer Berlin, Heidelberg, (2004).
  7. P. J. M. Laarhoven, E. H. L. Aarts, Simulated Annealing: Theory and Applications, Springer Dordrecht, (1987).
  8. M. A. Nielsen, I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, (2010).
  9. R. A. Horn, C. R. Johnson, Matrix Analysis, 2nd edn., Cambridge University Press, (2012).
  10. A. Montanaro, Quantum algorithms: an overview, npj Quantum Information 2 (1), pp. 15023, (2016).
  11. J. Preskill, Quantum Computing in the NISQ Era and Beyond, Quantum 2, pp. 79, (2018).
  12. D. Deutsch, Quantum theory, the Church–Turing principle and the universal quantum computer, Proceedings of the Royal Society A 400 (1818), pp. 97–117, (1985).
  13. F. Arute et al., Quantum supremacy using a programmable superconducting processor, Nature 574 (7779), pp. 505–510, (2019).

 

 

IZVOR: Proceedings of the 16th International Conference on Business Information Security BISEC’2025