어떤 특정한 경우에 양자 컴퓨터가 기존 컴퓨터를 능가합니까? 이것은 대답하기 어려운 질문입니다. 부분적으로는 오늘날의 양자 컴퓨터가 계산을 망치고 망칠 수 있는 오류로 인해 괴로워하는 까다롭기 때문입니다.
물론 한 가지 방법으로 그들은 이미 해냈습니다. 2019년 Google의 물리학자들은 발표 그들은 53큐비트 기계를 사용하여 양자 우위, 양자 컴퓨터가 실용적인 고전 알고리즘의 범위를 넘어서는 작업을 수행하는 지점을 표시하는 상징적 이정표입니다. 비슷한 시위 곧이어 중국 과학 기술 대학의 물리학자들이 발표했습니다.
그러나 특정 기계에 대한 실험 결과에 초점을 맞추기보다는 컴퓨터 과학자들은 고전적인 알고리즘이 양자 컴퓨터가 점점 더 커짐에 따라 따라갈 수 있는지 알고 싶어합니다. "희망은 결국 양자 측이 더 이상 경쟁이 없을 때까지 완전히 물러나는 것입니다."라고 말했습니다. 스콧 론슨, 오스틴에 있는 텍사스 대학의 컴퓨터 과학자.
그 일반적인 질문은 성가신 오류 때문에 여전히 대답하기 어렵습니다. (미래의 양자 기계는 양자 오류 수정, 하지만 그 능력은 아직 멀었습니다.) 오류가 수정되지 않은 경우에도 원하는 폭주 양자 이점을 얻을 수 있습니까?
대부분의 연구자들은 대답이 '아니오'라고 의심했지만 모든 경우에 대해 증명할 수는 없었습니다. 이제 종이 사전 인쇄 서버 arxiv.org에 게시된 컴퓨터 과학자 팀은 Google이 양자 우월성을 보여주기 위해 사용한 맞춤형 문제인 무작위 회로 샘플링에서 지속적인 양자 이점을 위해 오류 수정이 필요하다는 포괄적인 증거를 향한 주요 단계를 밟았습니다. 그들은 오류가 있을 때 무작위 회로 샘플링 실험을 시뮬레이션할 수 있는 고전적인 알고리즘을 개발함으로써 그렇게 했습니다.
Aaronson은 새로운 알고리즘이 Google과 같은 실제 실험을 시뮬레이션하는 데 실질적으로 유용하지 않다고 강조하면서 "이것은 아름다운 이론적 결과입니다."라고 말했습니다.
무작위 회로 샘플링 실험에서 연구자들은 큐비트 또는 양자 비트 배열로 시작합니다. 그런 다음 양자 게이트라는 작업을 통해 이러한 큐비트를 무작위로 조작합니다. 일부 게이트는 큐비트 쌍을 얽히게 합니다. 즉, 양자 상태를 공유하고 별도로 설명할 수 없습니다. 반복되는 게이트 레이어는 큐비트를 더 복잡한 얽힘 상태로 만듭니다.
그 양자 상태에 대해 알아보기 위해 연구자들은 어레이의 모든 큐비트를 측정합니다. 이로 인해 집단 양자 상태가 일반 비트(0과 1)의 임의 문자열로 붕괴됩니다. 가능한 결과의 수는 배열의 큐비트 수에 따라 빠르게 증가합니다. Google의 실험에서와 같이 53큐비트의 경우 거의 10조입니다. 그리고 모든 문자열의 가능성이 같은 것은 아닙니다. 무작위 회로에서 샘플링한다는 것은 이러한 측정을 여러 번 반복하여 결과의 기본이 되는 확률 분포의 그림을 구축하는 것을 의미합니다.
양자 이점에 대한 질문은 간단합니다. 확률 분포를 모방하는 것이 어렵습니까? 고전적인 알고리즘으로 얽힘을 사용하지 않습니까?
2019에서 연구자 증명 오류가 없는 양자 회로에 대한 대답은 '예'입니다. 오류가 없을 때 무작위 회로 샘플링 실험을 고전적으로 시뮬레이션하는 것은 실제로 어렵습니다. 연구자들은 서로 다른 문제의 상대적인 난이도를 분류하는 계산 복잡도 이론의 틀 내에서 작업했습니다. 이 분야에서 연구원들은 큐비트의 수를 53과 같은 고정된 숫자로 취급하지 않습니다. n증가할 숫자입니다.”라고 말했습니다. 아람 해로우, Massachusetts Institute of Technology의 물리학자. “그럼 당신은 묻고 싶을 것입니다. n 또는 다항식 n?” 이것은 알고리즘의 런타임을 분류하는 데 선호되는 방법입니다. n 충분히 커지면 기하급수적인 알고리즘 n 다항식 알고리즘보다 훨씬 뒤처짐 n. 이론가들이 고전 컴퓨터에는 어렵지만 양자 컴퓨터에는 쉬운 문제에 대해 말할 때, 그들은 다음과 같은 구별을 언급합니다. 최고의 고전 알고리즘은 기하급수적인 시간이 걸리는 반면 양자 컴퓨터는 다항식 시간으로 문제를 풀 수 있습니다.
그러나 2019년 논문은 불완전한 게이트로 인한 오류의 영향을 무시했습니다. 이로 인해 오류 수정 없이 무작위 회로 샘플링에 대한 양자 이점의 사례가 열렸습니다.
복잡도 이론가들이 하는 것처럼 큐비트의 수를 지속적으로 늘리는 것을 상상하고 오류도 설명하려는 경우 연구자들이 말하는 것처럼 회로 깊이를 증가시키면서 더 많은 게이트 레이어를 계속 추가할 것인지 여부를 결정해야 합니다. 큐비트 수를 늘리면서 회로 깊이를 상대적으로 얕은 XNUMX개의 레이어로 일정하게 유지한다고 가정합니다. 많은 얽힘이 발생하지 않으며 출력은 여전히 클래식 시뮬레이션에 적합합니다. 반면에 증가하는 큐비트 수를 따라잡기 위해 회로 깊이를 늘리면 게이트 오류의 누적 효과로 인해 얽힘이 사라지고 출력이 다시 고전적으로 시뮬레이션하기 쉬워집니다.
그러나 그 사이에 Goldilocks 영역이 있습니다. 새 논문 이전에는 큐비트 수가 증가하더라도 양자 이점이 여기서 살아남을 수 있는 가능성이 여전히 있었습니다. 이 중간 깊이 사례에서는 큐비트 수가 증가함에 따라 회로 깊이를 매우 느리게 늘립니다. 오류로 인해 출력이 꾸준히 저하되더라도 각 단계에서 고전적으로 시뮬레이션하기는 여전히 어려울 수 있습니다.
새로운 종이는 이 허점을 막습니다. 저자는 무작위 회로 샘플링을 시뮬레이션하기 위한 고전적인 알고리즘을 도출했으며 해당 실행 시간이 해당 양자 실험을 실행하는 데 필요한 시간의 다항식 함수임을 증명했습니다. 그 결과는 무작위 회로 샘플링에 대한 고전적 접근 방식과 양자 접근 방식 사이의 긴밀한 이론적 연결을 구축합니다.
새로운 알고리즘은 중간 심도 회로의 주요 클래스에 대해 작동하지만 기본 가정은 특정 얕은 알고리즘에 대해 무너져 효율적인 고전 시뮬레이션 방법을 알 수 없는 작은 간격을 남깁니다. 그러나 소수의 연구자들은 무작위 회로 샘플링이 이 남은 좁은 창에서 고전적으로 시뮬레이션하기 어렵다는 것을 증명할 것이라는 희망을 내세우고 있습니다. "나는 아주 작은 가능성을 준다"고 말했다. 빌 페퍼 만, 시카고 대학의 컴퓨터 과학자이자 2019년 이론 논문의 저자 중 한 명입니다.
결과는 무작위 회로 샘플링이 계산 복잡도 이론의 엄격한 기준에 의해 양자 이점을 제공하지 않을 것임을 시사합니다. 동시에 복잡도 이론가들이 무분별하게 효율적이라고 부르는 다항식 알고리즘이 실제로는 빠르지 않다는 사실을 보여줍니다. 새로운 고전 알고리즘은 오류율이 감소함에 따라 점진적으로 느려지고 양자 우위 실험에서 달성된 낮은 오류율에서는 너무 느려 실용적이지 않습니다. 오류가 없으면 완전히 고장이 나므로 이 결과는 이상적이고 오류가 없는 경우에 무작위 회로 샘플링을 고전적으로 시뮬레이션하는 것이 얼마나 어려운지에 대해 연구원들이 알고 있는 것과 모순되지 않습니다. 세르히오 보이소Google의 양자 우월성 연구를 주도하는 물리학자인 은 이 논문이 "무작위 회로 샘플링에 대한 훌륭한 확증에 가깝다"고 말합니다.
한 가지 점에서 모든 연구자들은 동의합니다. 새로운 알고리즘은 양자 오류 수정이 양자 컴퓨팅의 장기적인 성공에 얼마나 중요한지를 강조합니다. Fefferman은 "결국에는 그것이 해결책입니다."라고 말했습니다.
