양자 계산 복잡성에 대한 놀라운 새로운 증거는 재미있는 사고 실험으로 가장 잘 이해될 수 있습니다. 목욕을 한 다음 떠다니는 막대자석을 물에 버리십시오. 각 자석은 방향을 앞뒤로 뒤집어 이웃과 정렬하려고 합니다. 그것은 다른 자석을 밀고 당기고 그 대가로 밀고 당겨집니다. 이제 다음과 같이 답해 보십시오. 시스템의 최종 배열은 무엇입니까?
이 문제와 이와 유사한 다른 문제는 불가능할 정도로 복잡합니다. 수백 개 이상의 자석을 사용하면 컴퓨터 시뮬레이션이 답을 내놓는 데 터무니없는 시간이 걸릴 것입니다.
이제 그 자석을 양자화하십시오. 개별 원자는 양자 세계의 비잔틴 규칙에 종속됩니다. 짐작하시겠지만 문제는 더욱 어려워집니다. "상호작용이 더 복잡해진다" 헨리 위엔 컬럼비아 대학의. "XNUMX개의 인접한 '양자 자석'이 행복할 때 더 복잡한 제약이 있습니다."
이 단순해 보이는 시스템은 고전 버전과 양자 버전 모두에서 계산의 한계에 대한 탁월한 통찰력을 제공했습니다. 고전적 또는 비양자 시스템의 경우, 컴퓨터 과학의 획기적인 정리 우리를 더 멀리 데려갑니다. PCP 정리("확률적으로 확인 가능한 증명")라고 하는 이 정리는 자석의 최종 상태(또는 이와 관련된 측면)가 계산하기 매우 어려울 뿐만 아니라 그에 이르는 많은 단계도 어렵다고 말합니다. 상황의 복잡성은 훨씬 더 극적입니다. 즉, 최종 상태가 신비한 영역에 둘러싸여 있습니다.
아직 입증되지 않은 PCP 정리의 또 다른 버전은 특히 양자 사례를 다룹니다. 컴퓨터 과학자들은 양자 PCP 추측이 사실이라고 의심하고 있으며, 이를 증명하면 양자 문제의 복잡성에 대한 우리의 이해가 바뀔 것입니다. 이것은 양자 계산 복잡성 이론에서 가장 중요한 미해결 문제로 간주됩니다. 그러나 지금까지는 도달할 수 없는 상태로 남아 있습니다.
XNUMX년 전, 두 명의 연구자가 우리가 거기에 도달하는 데 도움이 되는 중간 목표를 확인했습니다. 그들은 생각해 냈어 더 간단한 가설양자 PCP 추측이 참이면 참이어야 하는 NLTS(저에너지 사소한 상태 없음) 추측으로 알려져 있습니다. 이를 증명한다고 해서 양자 PCP 추측을 증명하는 것이 반드시 더 쉬워지는 것은 아니지만 가장 흥미로운 질문 중 일부는 해결될 것입니다.
그런 다음 지난 달에 세 명의 컴퓨터 과학자가 NLTS 추측 증명. 그 결과는 컴퓨터 과학과 양자 물리학에 놀라운 영향을 미칩니다.
"매우 흥미진진하다"고 말했다 도리트 아하로노프 예루살렘 히브리 대학교의 "그것은 사람들이 양자 PCP 추측의 더 어려운 문제를 조사하도록 장려할 것입니다."
새로운 결과를 이해하려면 원자 세트와 같은 양자 시스템을 그리는 것으로 시작하십시오. 각 원자는 스핀이라고 하는 속성을 가지고 있으며, 이는 축을 따라 가리키는 자석의 정렬과 다소 유사합니다. 그러나 자석의 정렬과 달리 원자의 스핀은 서로 다른 방향이 동시에 혼합된 상태일 수 있으며 중첩이라고 알려진 현상입니다. 또한, 먼 지역에서 온 다른 원자의 스핀을 고려하지 않고 한 원자의 스핀을 설명하는 것은 불가능할 수 있습니다. 이런 일이 발생하면 상호 연결된 원자가 양자 얽힘 상태에 있다고합니다. 얽힘은 놀랍지만 깨지기 쉽고 열 상호 작용에 의해 쉽게 파괴됩니다. 시스템의 열이 많을수록 얽히기가 더 어려워집니다.
이제 절대 영도에 도달할 때까지 원자 무리를 냉각시키는 것을 상상해 보십시오. 시스템이 냉각되고 얽힘 패턴이 더 안정되면 에너지가 감소합니다. 가능한 가장 낮은 에너지 또는 "지상 에너지"는 전체 시스템의 복잡한 최종 상태에 대한 간결한 설명을 제공합니다. 또는 적어도 계산할 수 있다면 그렇게 할 것입니다.
1990년대 후반부터 연구자들은 특정 시스템의 경우 이 지상 에너지를 합리적인 시간 내에 계산할 수 없다는 사실을 발견했습니다.
그러나 물리학자들은 시스템이 더 따뜻하고 덜 얽히며 따라서 더 간단할 것이기 때문에 지면 에너지에 가까운 에너지 준위(그러나 실제로는 그렇지 않음)를 계산하기가 더 쉬워야 한다고 생각했습니다.
컴퓨터 과학자들은 동의하지 않았습니다. 고전적인 PCP 정리에 따르면 최종 상태에 가까운 에너지는 최종 에너지 자체만큼 계산하기 어렵습니다. 따라서 PCP 정리의 양자 버전이 사실이라면, 기저 에너지에 대한 전구체 에너지는 기저 에너지만큼 계산하기 어려울 것이라고 말할 것입니다. 고전적인 PCP 정리가 참이기 때문에 많은 연구자들은 양자 버전도 참이어야 한다고 생각합니다. Yuen은 "확실히 양자 버전은 사실이어야 합니다.
그러한 정리의 물리적 의미는 심오할 것입니다. 이는 물리학자들의 기대와 완전히 반대되는 고온에서도 얽힘을 유지하는 양자 시스템이 있음을 의미합니다. 그러나 아무도 그러한 시스템이 존재한다는 것을 증명할 수 없습니다.
2013년, 캘리포니아 산타 바바라에 있는 Microsoft Research의 Station Q에서 일하는 Michael Freedman과 Matthew Hastings는 문제의 범위를 좁혔습니다. 그들은 가장 낮은 에너지와 거의 가장 낮은 에너지를 컴퓨터가 시뮬레이션하는 데 필요한 회로의 양이라는 단 하나의 측정 기준으로 계산하기 어려운 시스템을 찾기로 결정했습니다. 이러한 양자 시스템을 찾을 수 있다면 가장 낮은 에너지에서도 풍부한 얽힘 패턴을 유지해야 합니다. 그러한 시스템의 존재는 양자 PCP 추측을 증명하지 않을 것입니다. 고려해야 할 다른 경도 메트릭이 있을 수 있습니다. 그러나 그것은 진행으로 간주될 것입니다.
컴퓨터 과학자들은 그러한 시스템을 몰랐지만 어디로 가야 하는지 알고 있었습니다. 양자 오류 수정이라고 하는 연구 분야에서 연구자들은 교란으로부터 원자를 보호하도록 설계된 얽힘의 조리법을 만드는 것입니다. 각각의 레시피는 코드로 알려져 있으며, 크고 작은 코드가 많이 있습니다.
2021년 말 컴퓨터 과학자들은 중대한 돌파구를 마련했다 본질적으로 이상적인 성격의 양자 오류 수정 코드를 생성합니다. 그 후 몇 달 동안 다른 여러 연구자 그룹이 이러한 결과를 바탕으로 다른 버전을 만들었습니다.
지난 XNUMX년 동안 관련 프로젝트에서 공동 작업을 한 새 논문의 세 저자는 새로운 코드 중 하나가 Freedman과 Hastings가 가정한 종류의 양자 시스템을 만드는 데 필요한 모든 속성을 가지고 있음을 증명하기 위해 모였습니다. . 그렇게 함으로써 그들은 NLTS 추측을 증명했다.
그들의 결과는 얽힘이 반드시 물리학자들이 생각하는 것만큼 깨지기 쉽고 온도에 민감한 것은 아니라는 것을 보여줍니다. 그리고 이것은 양자 PCP 추측을 지지하여, 지상 에너지에서 멀리 떨어져 있어도 양자 시스템의 에너지는 계산하는 것이 사실상 불가능할 수 있음을 시사합니다.
“사실일 것 같지 않은 것이 사실이라고 말해줍니다.” 이삭 김 캘리포니아 대학교 데이비스 교수. "비록 아주 이상한 시스템이긴 하지만."
연구원들은 완전한 양자 PCP 추측을 증명하기 위해 다른 기술 도구가 필요할 것이라고 믿습니다. 그러나 그들은 현재의 결과가 그들에게 더 가까워질 것이라고 낙관적인 이유를 보고 있습니다.
그들은 아마도 새로 발견된 NLTS 양자 시스템(이론적으로는 가능하지만)이 실제로 자연에서 생성될 수 있는지, 그리고 어떻게 생겼는지에 대해 가장 흥미를 느꼈을 것입니다. 현재의 결과에 따르면, 그것들은 실험실에서 한 번도 생성된 적이 없고 천문학적인 수의 원자를 사용해서만 만들 수 있는 장거리 얽힘의 복잡한 패턴을 요구할 것입니다.
"이것은 고도로 엔지니어링 된 개체입니다."라고 말했습니다. 친메이 니르케, University of California, Berkeley의 컴퓨터 과학자이자 새 논문의 공동 저자입니다. 아누락 안슈 하버드 대학교와 니콜라스 브루크만 유니버시티 칼리지 런던.
Anshu는 "정말 멀리 떨어진 큐비트를 결합할 수 있는 능력이 있다면 시스템을 실현할 수 있을 것이라고 믿습니다."라고 말했습니다. "하지만 저에너지 스펙트럼으로 가는 또 다른 여정이 있습니다." 브루크만(Breuckmann)은 “우주의 일부가 NLTS일 수도 있습니다. 모르겠어요."
