일정 규모의 양자컴퓨터들이 속속 개발되고 있다. 크기와 성능이 제한적이어서 계산범용성을 갖지 못하지만, 특정 계산문제 (디지털 알고리듬이 비효율적인 문제)에 활용될 수 있을지가 많은 관심을 받는다. 계산복잡도가 NP(비결정적 다항)로 분류되는 문제들은 디지털 컴퓨팅의 알고리듬으로는 효율적으로 계산할 수 없다. 따라서 양자컴퓨터를 이용하여 NP-문제, 특히 모든 NP-문제에 대한 다항 시간 환원성을 갖는 NP-완전 문제들을 계산할 수 있을지가 주목을 받는다. 본 발표에서는 리드버그 원자 시스템을 이용하여 NP-완전문제의 하나인 최대독립집합 문제를 "계산"한 실험연구를 소개한다. 그리고 다른 NP-문제로의 응용과 디지털 컴퓨터의 계산한계에 도전하기 위한 성능향상에 관하여 논의한다.

(One after another, scalable quantum computers are being developed. While their computational capabilities are limited, due to their scale and performance, whether they can be used for specific computational problems, especially the problems in which digital algorithms are inefficient, is of great interest. Problems whose computational complexity is classified as NP (non-deterministic polynomial) cannot be efficiently calculated by digital computing algorithms. Therefore, attention is focused on whether quantum computers can be used to compute NP-problems, especially NP-complete problems with polynomial time reducibility to all other NP-problems. In this presentation, we introduce our experiments of using Rydberg atom arrays to "solve" one of the NP-complete problems, the maximum independent set problem. We then discuss applications to other NP-problems and performance requirements to challenge the computational limits of digital computers.)