Decomposição em Produto de Kronecker para Compilação Quântica
Resumo
Neste trabalho, introduzimos um método para a Decomposição de Produto de Kronecker de matrizes unitárias, capaz de decompor uma matriz unitária separável em tempo O(N2 logN), sem exigir conhecimento prévio sobre as dimensões da matriz ou suas partições de qubits. A proposta representa uma melhoria significativa em relação ao tempo O(N3) dos algoritmos presentes na literatura. Aplicamos o método à compilação de unitárias quânticas, resultando em uma redução empírica na contagem de portas do circuito e em uma melhoria significativa nos tempos de compilação. Validamos os resultados com experimentos computacionais para verificar reduções no tempo de compilação e na contagem de CNOT ao implementar portas unitárias.
Referências
Araujo, I. F., Araújo, I. C. S., da Silva, L. D., Blank, C., and da Silva, A. J. (2023). Quantum computing library. [link]. Version 0.0.21.
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., and Weinfurter, H. (1995). Elementary gates for quantum computation. Physical Review A, 52:3457–3467.
Batselier, K. and Wong, N. (2017). A constructive arbitrary-degree kronecker product decomposition of tensors. Numerical Linear Algebra with Applications, 24(5).
Bergholm, V., Izaac, J., Schuld, M., Gogolin, C., et al. (2018). PennyLane: Automatic differentiation of hybrid quantum-classical computations.
Bergholm, V., Vartiainen, J. J., Möttönen, M., and Salomaa, M. M. (2005). Quantum circuits with uniformly controlled one-qubit gates. Phys. Rev. A, 71:052330.
Cai, C., Chen, R., and Xiao, H. (2022). Hybrid kronecker product decomposition and approximation. Journal of Computational and Graphical Statistics, 32(3):838–852.
Cormen, T., Leiserson, C., Rivest, R., and Stein, C. (2022). Introduction to Algorithms, fourth edition. MIT Press.
de Carvalho, J. A., Batista, C. A., de Veras, T. M. L., Araujo, I. F., and da Silva, A. J. (2024). Quantum multiplexer simplification for state preparation.
Developers, C. (2025). Cirq.
Fahrbach, M., Fu, G., and Ghadiri, M. (2022). Subquadratic kronecker regression with applications to tensor decomposition. Advances in Neural Information Processing Systems, 35:28776–28789.
Iten, R., Colbeck, R., Kukuljan, I., Home, J., and Christandl, M. (2016). Quantum circuits for isometries. Physical Review A, 93(3):032318.
Javadi-Abhari, A., Treinish, M., Krsulich, K., Wood, C. J., Lishman, J., Gacon, J., Martiel, S., Nation, P., Bishop, L. S., Cross, A. W., Johnson, B. R., and Gambetta, J. M. (2024). Quantum computing with Qiskit.
Kamm, J. and Nagy, J. G. (2000). Optimal kronecker product approximation of block toeplitz matrices. SIAM Journal on Matrix Analysis and Applications, 22(1):155–172.
Nielsen, M. A. and Chuang, I. L. (2010). Quantum computation and quantum information. Cambridge university press.
Paleologu, C., Benesty, J., and Ciochină, S. (2018). Linear system identification based on a kronecker product decomposition. IEEE/ACM Transactions on Audio, Speech, and Language Processing, 26(10):1793–1808.
Preskill, J. (2018). Quantum computing in the nisq era and beyond. Quantum, 2:79.
S., J., Yadav, S. K., and George, N. V. (2024). Adaptive low-rank doa estimation using complex kronecker product decomposition. IEEE Transactions on Vehicular Technology, 73(7):10726–10731.
Shende, V., Bullock, S., and Markov, I. (2006). Synthesis of quantum-logic circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(6):1000–1010.
Tarjan, R. E. (1975). Efficiency of a good but not linear set union algorithm. J. ACM, 22(2):215–225.
Van Loan, C. F. and Pitsianis, N. (1993). Approximation with kronecker products. In Moonen, M. S., Golub, G. H., and De Moor, B. L. R., editors, Linear Algebra for Large Scale and Real-Time Applications, volume 232 of NATO ASI Series, pages 293–314. Springer, Dordrecht.
Virtanen, P. et al. (2020). SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261–272.
Wang, X., Huang, G., Benesty, J., Chen, J., and Cohen, I. (2021). Time difference of arrival estimation based on a kronecker product decomposition. IEEE Signal Processing Letters, 28:51–55.
Wu, Y. (2023). A new method of kronecker product decomposition. Journal of Mathematics, 2023.
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., and Weinfurter, H. (1995). Elementary gates for quantum computation. Physical Review A, 52:3457–3467.
Batselier, K. and Wong, N. (2017). A constructive arbitrary-degree kronecker product decomposition of tensors. Numerical Linear Algebra with Applications, 24(5).
Bergholm, V., Izaac, J., Schuld, M., Gogolin, C., et al. (2018). PennyLane: Automatic differentiation of hybrid quantum-classical computations.
Bergholm, V., Vartiainen, J. J., Möttönen, M., and Salomaa, M. M. (2005). Quantum circuits with uniformly controlled one-qubit gates. Phys. Rev. A, 71:052330.
Cai, C., Chen, R., and Xiao, H. (2022). Hybrid kronecker product decomposition and approximation. Journal of Computational and Graphical Statistics, 32(3):838–852.
Cormen, T., Leiserson, C., Rivest, R., and Stein, C. (2022). Introduction to Algorithms, fourth edition. MIT Press.
de Carvalho, J. A., Batista, C. A., de Veras, T. M. L., Araujo, I. F., and da Silva, A. J. (2024). Quantum multiplexer simplification for state preparation.
Developers, C. (2025). Cirq.
Fahrbach, M., Fu, G., and Ghadiri, M. (2022). Subquadratic kronecker regression with applications to tensor decomposition. Advances in Neural Information Processing Systems, 35:28776–28789.
Iten, R., Colbeck, R., Kukuljan, I., Home, J., and Christandl, M. (2016). Quantum circuits for isometries. Physical Review A, 93(3):032318.
Javadi-Abhari, A., Treinish, M., Krsulich, K., Wood, C. J., Lishman, J., Gacon, J., Martiel, S., Nation, P., Bishop, L. S., Cross, A. W., Johnson, B. R., and Gambetta, J. M. (2024). Quantum computing with Qiskit.
Kamm, J. and Nagy, J. G. (2000). Optimal kronecker product approximation of block toeplitz matrices. SIAM Journal on Matrix Analysis and Applications, 22(1):155–172.
Nielsen, M. A. and Chuang, I. L. (2010). Quantum computation and quantum information. Cambridge university press.
Paleologu, C., Benesty, J., and Ciochină, S. (2018). Linear system identification based on a kronecker product decomposition. IEEE/ACM Transactions on Audio, Speech, and Language Processing, 26(10):1793–1808.
Preskill, J. (2018). Quantum computing in the nisq era and beyond. Quantum, 2:79.
S., J., Yadav, S. K., and George, N. V. (2024). Adaptive low-rank doa estimation using complex kronecker product decomposition. IEEE Transactions on Vehicular Technology, 73(7):10726–10731.
Shende, V., Bullock, S., and Markov, I. (2006). Synthesis of quantum-logic circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(6):1000–1010.
Tarjan, R. E. (1975). Efficiency of a good but not linear set union algorithm. J. ACM, 22(2):215–225.
Van Loan, C. F. and Pitsianis, N. (1993). Approximation with kronecker products. In Moonen, M. S., Golub, G. H., and De Moor, B. L. R., editors, Linear Algebra for Large Scale and Real-Time Applications, volume 232 of NATO ASI Series, pages 293–314. Springer, Dordrecht.
Virtanen, P. et al. (2020). SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261–272.
Wang, X., Huang, G., Benesty, J., Chen, J., and Cohen, I. (2021). Time difference of arrival estimation based on a kronecker product decomposition. IEEE Signal Processing Letters, 28:51–55.
Wu, Y. (2023). A new method of kronecker product decomposition. Journal of Mathematics, 2023.
Publicado
19/07/2026
Como Citar
AZEVEDO, Thiago Melo D.; LANGELOH, Gabriel M.; BRITO, Samuraí; SILVA, Adenilton J. da.
Decomposição em Produto de Kronecker para Compilação Quântica. In: SIMPÓSIO BRASILEIRO DE COMPUTAÇÃO E COMUNICAÇÃO QUÂNTICAS (SBCCQ), 1. , 2026, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 13-24.
DOI: https://doi.org/10.5753/sbccq.2026.23567.
