Limits and possibilities of quantum computational complexity
DOI:
https://doi.org/10.23925/1984-3585.2024i2930p108-130Keywords:
quantum computing, computational complexity, P and BQP classes, quantum algorithms, hybrid paradigmAbstract
This paper explores the impact of quantum computing on computational complexity theory, with a focus on the classes P e BQP, examining how quantum paradigms challenge classical problem categorizations. By analyzing Shor’s and Grover’s algorithms, the study discusses how these quantum algorithms expand the scope of solvable problems, previously considered intractable within polynomial time for classical systems. The analysis provides a historical review of complexity classes, covering the emergence and significance of classes P and NP and the importance of quantum algorithms for traditionally intractable problems. Additionally, the article addresses the introduction of hybrid theories that integrate classical and quantum methods, such as the Variational Quantum Eigensolver (VQE) and Quantum Annealing, highlighting the efficiency of these approaches in solving complex optimization problems. Discussions on probabilistic classes BPP and PP are also central to understanding the role of probability in quantum algorithms, an intrinsic feature of the quantum computing model. The study is justified by the ongoing need to reevaluate the foundations of complexity theory considering quantum advancements, which redefine theoretical and practical boundaries. While quantum computing still faces challenges, such as qubit stability, hybrid paradigm proposals offer promising paths to address high-complexity problems, signaling a transition toward a mixed computational era with the potential to revolutionize problem-solving in the 21st century.
References
AARONSON, Scott. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, v. 2, n. 4, p. 1–9, 31 dez. 2021. Disponível em https://arxiv.org/pdf/2109.06917. Acesso em 30 de outubro de 2024.
ARORA, Sanjeev; BARAK, Boaz. Computational complexity: A modern approach. Cambridge: Cambridge University Press, 2009.
BERNSTEIN, Ethan.; VAZIRANI, Umesh. Quantum complexity theory. Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing – STOC ‘93, p. 11-20, 1993. Disponível em: <https://doi.org/10.1137/S0097539796300921>. Acesso em 30 de outubro de 2024.
CHENG, Sheng-Tzong; WANG, Chun-Yen. Quantum switching and quantum merge sorting. IEEE Transactions on Circuits and Systems I: Regular Papers, v. 53, n. 2, p. 316-325, 2006. Disponível em: <https://ieeexplore.ieee.org/document/1593938>. Acesso em 30 de outubro de 2024.
FREIRE JUNIOR, Olival; GRECA, Ilena M. Informação e teoria quântica. Scientiae Studia, v. 11, n. 1, p. 11–33, jan. 2013. Disponível em: <https://www.scielo.br/j/ss/a/gx6mgj96M9q96XVkrkh7bSp>. Acesso em 30 de outubro de 2024.
GILL, Sukhpal Singh, et al. Quantum computing: A taxonomy, systematic review and future directions. Software: Practice and Experience, 52, p. 66-114, 2021. Disponível em: <https://onlinelibrary.wiley.com/doi/epdf/10.1002/spe.3039>. Acesso em 30 out., 2024.
HEY, Tony. Quantum computing: an introduction. Computing & Control Engineering Journal, v. 10, n. 3, p. 105-112, 1999. Disponível em: https://www.researchgate.net/publication/3363605_Quantum_computing_An_introduction. Acesso em 30 de outubro de 2024.
LI, Jian et al. Fidelity-guaranteed entanglement routing in quantum networks, IEEE Transactions on Communications, v. 70, n. 10, p. 6748-6763, 2022. Disponível em: <https://arxiv.org/abs/2111.07764>. Acesso em 30 de outubro de 2024.
MARGENSTERN, Maurice. Frontier between decidability and undecidability: a survey. Theoretical Computer Science, v. 231, n. 2, p. 217-251, 2000. Disponível em: https://core.ac.uk/download/pdf/82133923.pdf. Acesso em 30 de outubro de 2024.
McCLEAN, Jarrod R. et al. The theory of variational hybrid quantum-classical algorithms. New Journal of Physics, v. 18, n. 2, 20 p, 2016. Disponível em: <https://arxiv.org/abs/1509.04279>. Acesso em 30 de outubro de 2024.
MOHR, Austin. Quantum computing in complexity theory and theory of computation, Carbondale IL, 2014, Disponível em: <http://austinmohr.com/work/files/complexity.pdf>. Acesso em 30 de outubro de 2024.
RAYMER, Michael G.; MONROE, Chistopher. The US National Quantum Initiative. Quantum Science Technology, v. 4, n. 20504, p. 1-6, 2019. Disponível em: <https://iopscience.iop.org/article/10.1088/2058-9565/ab0441>. Acesso em 30 de outubro de 2024.
STOCKMEYER, Larry. Classifying the computational complexity of problems. Journal of Symbolic Logic, v. 52, n. 1, p. 1-43, 1987. Disponível em: <https://www.jstor.org/stable/2273858>. Acesso 30 out., 2024.
WATROUS, John. Quantum computational complexity, 2008. Disponível em: <https://arxiv.org/abs/0804.3401>. Acesso em 30 de outubro de 2024.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 TECCOGS: Revista Digital de Tecnologias Cognitivas
This work is licensed under a Creative Commons Attribution 4.0 International License.
Esta revista oferece acesso livre imediato ao seu conteúdo de acordo com a licença CC BY 4.0, em conformidade com a definição de acesso público do Directory of Open Access Journals (DOAJ).
Ao submeter um texto à TECCOGS, os autores asseguram que o material submetido à avaliação e eventual publicação não infringe de modo algum qualquer direito proprietário ou copyright de outros. Com a submissão, o autor transfere em efetivo os direitos de publicação do artigo para a TECCOGS. A transferência de copyright cobre os direitos exclusivos de publicação e distribuição do artigo, incluindo reimpressões ou quaisquer outras reproduções de natureza similar, além de traduções. Os autores mantém o direito de usar todo ou partes deste texto em trabalhos futuros de sua autoria e de conceder ou recusar a permissão a terceiros para republicar todo ou partes do texto ou de suas traduções. Para republicar números da revista na íntegra, qualquer interessado precisa obter permissão por escrito tanto dos autores como também dos editores da TECCOGS. A TECCOGS por si só pode conceder direitos relativos a emissões de periódicos como um todo.
Imagens com direitos autorais pertencentes a terceiros, que não foram concedidos ao autor do texto, devem ser utilizadas somente quando necessárias à análise e ao argumento da pesquisa, sempre indicando as respectivas fontes e autoria. A TECCOGS dispensa o uso de imagens meramente ilustrativas. Se desejar ilustrar um conceito, o autor deve indicar, em forma de URL ou referência bibliográfica, uma referência em que a ilustração esteja disponível.
---------------------------------------------------------------------------------
This journal offers free immediate access to its content under CC BY 4.0, in accordance with Directory of Open Access Journals' (DOAJ) definition of Open Acess.
When submitting a text to TECCOGS, authors ensure that the material submitted for evaluation and eventual publication does not infringe any proprietary right or copyright. Upon submission, authors effectively transfer the publication rights of the article to TECCOGS. The copyright transfer covers the exclusive rights of publication and distribution of the article, including reprints or any other reproduction of similar nature, in addition to translations. Authors retain the right to use all or parts of the text in future works of their own, as well as to grant or refuse permission to third parties to republish all or parts of the text or its translations. In order to fully republish issues of the magazine, anyone interested must obtain written permission from both the authors and the editors of TECCOGS. TECCOGS alone can grant rights relating to issues of journals as a whole.
Images whose copyright belongs to third parties that have not been granted to the author of the text should be used only when essential for the analysis and argument, always indicating theirs respective sources and authorship. TECCOGS dismisses any use of merely illustrative images. To illustrate a concept, the author must indicate, in the form of a URL or bibliographic reference, a source in which the illustration is available.
