양자우월

Quantum supremacy

양자 컴퓨팅에서 양자 우위 또는 양자 우위성은 프로그램 가능한 양자 소자가 어떤 고전적 컴퓨터도 어느 실현 가능한 시간 내에 해결할 수 없는 문제를 (문제의 유용성과 무관하게) 해결할 수 있다는 것을 증명하는 목적이다.[1][2][3]개념적으로 양자 우위는 강력한 양자 컴퓨터 구축이라는 공학적 과제와 양자 컴퓨터가 해결할 수 있는 문제를 찾고 그 과제에 대해 가장 잘 알려져 있거나 가능한 고전 알고리즘에 비해 초특급 속도를 높이는 계산 복합적 이데올로기적 과제를 모두 포함한다.[4][5]이 용어는 2012년 존 프레스킬에 의해 만들어졌지만 양자 시스템을 시뮬레이션하기 위한 양자 계산 우위의 개념은 유리 마닌(1980년)[7]과 리처드 파인먼(1981)의 양자 계산 제안으로 거슬러 올라간다.[1][6][8]양자 우위성을 입증하기 위한 제안의 예로는 아론손과 아큐포프의 보손 샘플링 제안,[9] 디웨이브의 전문화된 좌절된 클러스터 루프 문제,[10] 랜덤 양자 회로의 출력 샘플링 등이 있다.[11][12]

양자우월주의의 주목할 만한 특성은 양자 컴퓨터가 어떤 유용한[13] 작업을 수행하거나 둘 다 장기 [14]목표인 고품질 양자오차보정을 사용할 필요가 없기 때문에 단기 양자컴퓨터로 실현 가능한 것이다.[6][2]따라서, 연구자들은 양자 컴퓨팅의 미래 상업적 실행가능성과 관련성이 상대적으로 적은 양자 패권을 주로 과학적 목표로 보고 있다.[2]기존의 어떤 컴퓨터도 실현할 수 없는 작업을 수행할 수 있는 양자컴퓨터 구축이라는 이 목표는 클래식 컴퓨터나 시뮬레이션 알고리즘이 향상되면 더 어려워질 수 있기 때문에 양자 패권을 일시적으로 혹은 반복적으로 달성할 수 있어 양자 패권을 달성해야 한다는 주장이 상당 부분 집중 검토 대상이 될 수 있다.[15][16]

배경

20세기 양자 패권

1936년 앨런 튜링은 1900년 힐버트 문제에 대한 응답으로 "계산 가능한 숫자에 대하여"라는 논문을 발표했다.[17]튜링의 논문은 그가 "유니버설 컴퓨팅 머신"이라고 부르는 것을 기술했는데, 후에 튜링 머신으로 알려지게 되었다.1980년 폴 베니오프는 튜링의 논문을 활용하여 양자컴퓨팅의 이론적 실현 가능성을 제안하였다.그의 논문 "물리적 시스템으로서의 컴퓨터:'튜링 머신으로 대표되는 컴퓨터의 현미경 양자역학 해밀턴식 모델'[18]은 소멸된 에너지가 임의로 작은 한 양자컴퓨팅의 가역성을 보여줄 수 있음을 최초로 입증했다.1981년 리처드 파인만은 양자역학이 고전적인 장치에서는 시뮬레이션될 수 없다는 것을 보여주었다.[19]그는 강연에서 "자연은 고전적인 것이 아니고 자연에 대한 시뮬레이션을 하고 싶다면 양자역학적으로 만드는 것이 좋을 것"이라고 유명한 말을 전했다.[19]그 직후, 데이비드 도이치는 양자 튜링 기계에 대한 설명을 생산했고 양자 컴퓨터에서 실행하기 위해 만들어진 알고리즘을 설계했다.[20]

1994년, 피터 쇼르가 쇼어의 알고리즘을 공식화하면서 양자 패권을 향한 더 많은 진전이 이루어졌고, 다항식 시간에 정수를 인수하는 방법을 합리화하였다.[21]이후 1995년 크리스토퍼 먼로와 데이비드 위닝랜드는 양자 논리 게이트의 첫 시연인 '기본 양자 논리 게이트의 시연'[22]을 발표하면서 특히 2비트 "제어-NOT"를 기록했다.1996년, Lov Grover는 그의 알고리즘인 Grover's Algorithm을 그의 논문 "데이터베이스 검색을 위한 빠른 양자 기계 알고리즘"[23]에 발표한 후 양자 컴퓨터 조작에 관심을 갖게 되었다.1998년 조나단 A. 존스와 미셸 모스카는 '핵자기공명 양자컴퓨터에서의 독일어 문제 해결을 위한 양자 알고리즘 구현'[24]을 발표해 양자 알고리즘의 첫 시범을 보였다.

21세기의 진보

양자 패권을 향한 엄청난 진보는 2000년대에 최초의 5쿼빗 핵자기 공명 컴퓨터(2000년), 쇼르의 정리 시연(2001년), 군집화된 양자 컴퓨터에서의 독일어 알고리즘 구현(2007년)에서 이루어졌다.[25]2011년 브리티시 컬럼비아에 있는 버나비의 D-Wave Systems of British Columbia는 양자 컴퓨터를 상업적으로 판매한 첫 번째 회사가 되었다.[26]2012년 물리학자인 난양 쉬는 143을 인수하기 위해 개선된 부차적 인수 알고리즘을 사용함으로써 획기적인 성과를 거두었다.그러나 쉬가 사용한 방법에는 반대가 있었다.[27]이 같은 성과를 거둔 지 얼마 되지 않아 구글은 첫 양자컴퓨터를 구입했다.[28]

구글은 49개의 초전도 쿼트로 2017년 말 이전에 양자 패권을 입증하겠다는 계획을 발표한 바 있다.[29]인텔은 2018년 1월 초 비슷한 하드웨어 프로그램을 발표했다.[30]IBM은 2017년 10월 클래식 슈퍼컴퓨터에 56쿼트의 시뮬레이션을 시연해 양자 우위 확립에 필요한 연산력을 높였다.[31]2018년 11월, 구글은 NASA와 "구글 퀀텀 프로세서에서 실행되는 양자 회로의 결과를 분석하는 파트너십을 발표했다.구글의 하드웨어 검증과 양자 패권에 대한 기준 확립을 지원하기 위해 고전적 시뮬레이션과 비교를 제공한다.[32]2018년 발표된 이론적 연구에서는 오류율을 충분히 낮게 밀어낼 수 있다면 '7×7큐빗의 2차원 격자 및 약 40클럭 사이클'로 양자 패권이 가능해야 한다는 것을 제시하고 있다.[33]콴타 매거진은 2019년 6월 18일 네븐의 법칙에 따라 2019년에 양자 패권이 일어날 수 있다고 제안했다.[34]파이낸셜타임스(FT)는 2019년 9월 20일 "구글이 54쿼트의 배열로 양자 패권에 도달했다고 주장하는데, 이 중 53쿼트는 슈퍼컴퓨터를 완성하는 데 약 1만년이 걸리는 200초 만에 일련의 작업을 수행하는 데 사용되었다"고 보도했다.[35][36]10월 23일 구글은 이러한 주장을 공식 확인했다.[37][38][39]IBM은 일부 주장이 과도하다고 답변하고, 기존 슈퍼컴퓨터가 컴퓨팅 속도를 극대화하기 위해 사용할 수 있는 기법을 나열하며 1만년이 아닌 2.5일이 걸릴 수 있다고 제안했다.IBM의 대응은 당시 가장 강력한 슈퍼컴퓨터였던 서밋이 IBM에 의해 만들어진 것과 관련이 있다.[40][15][41]

2020년 12월, 지안웨이 판이 이끄는 중국과학기술대학(USTC)에 기반을 둔 그룹이 광자 양자 컴퓨터 주장(周長)[42][43][44]으로 76개 광자에 가우스보손 샘플링을 실시하여 양자 우위에 올랐다.이 논문은 양자 컴퓨터가 20초 안에 생성하는 샘플의 수를 생성하기 위해서는 고전적인 슈퍼 컴퓨터가 6억 년의 연산을 필요로 할 것이라고 기술하고 있다.[3]

2021년 10월 USTC 팀은 주즈항 2.0과 주총지라는 슈퍼컴퓨터 2대를 구축해 다시 양자 우위를 점했다고 보고했다.광 기반 주항 2.0은 가우스 보손 샘플링을 구현하여 144-모드 광학 간섭계에서 113개의 광자를 검출하고 샘플링 속도는 10으로24 기존 주항 대비 광자 37개와 크기 10개의 차이를 보였다.[45][46]Zuchongzhi는 효율적인 작동을 위해 극도로 낮은 온도에서 보관되어야 하는 프로그램 가능한 초전도 양자 컴퓨터로서, 66개의 트랜스포턴의 튜닝 가능한 커플링 아키텍처에서 56Qbit를 얻기 위해 무작위 회로 샘플링을 사용한다. 이는 구글의 Sycamore 2019 성취보다 3Qbit 향상되었고, 이는 더 큰 계산 비용을 의미한다.2-3단계의 [47][48][49]고전적 시뮬레이션세 번째 연구는 주총지 2.1이 "고전 시뮬레이션에서 "사이카모어의 그것보다 약 6배 더 어려운" 샘플링 과제를 완료했다고 보고했다.[50]

계산 복잡성

주요 기사:양자 복잡성 이론

복잡성 주장은 문제를 해결하는 데 필요한 일부 자원(일반적으로 시간 또는 메모리)의 양이 입력 크기에 따라 어떻게 확장되는지를 다룬다.이 설정에서 문제는 입력된 문제 인스턴스(이진 문자열)와 반환된 솔루션(상응 출력 문자열)으로 구성되며, 리소스는 지정된 기본 운영, 메모리 사용량 또는 통신을 가리킨다.로컬 연산 모음은 컴퓨터가 출력 문자열을 생성할 수 있도록 허용한다.회로 모델과 그에 상응하는 연산은 고전적 및 양자적 문제를 모두 기술하는데 유용하다. 고전적 회로 모델은 AND 게이트, OR 게이트, NOT 게이트와 같은 기본 연산으로 구성되는 반면, 양자 모델은 고전적 회로와 단일적 연산의 적용으로 구성된다.유한한 세트의 고전적 관문과 달리, 통일적 작전의 지속적인 성격으로 인해 양자 관문이 무한히 존재한다.고전적인 경우와 양자적인 경우 모두 복잡성이 증가하면서 문제 크기가 증가한다.[51]고전적 계산 복잡성 이론의 연장선으로서 양자 복잡성 이론은 물리적인 양자 컴퓨터를 구축하거나 정합성과 소음을 다루는 어려움에 대한 설명 없이 이론적인 보편적 양자 컴퓨터가 성취할 수 있는 것을 고려한다.[52]양자 정보는 고전적인 정보의 일반화이기 때문에 양자 컴퓨터는 어떤 고전적인 알고리즘도 시뮬레이션할 수 있다.[52]

양자 복잡도 등급은 공통 양자 계산 모델을 공유하는 일련의 문제들로, 각 모델은 지정된 자원 제약조건을 포함하고 있다.회로 모델은 양자 복잡도 클래스를 설명하는 데 유용하다.[53]가장 유용한 양자 복잡도 등급은 범용 양자컴퓨터가 다항 시간에 해결할 수 있는 의사결정 문제의 등급인 BQP(경계오류 양자다항시간)이다.[54]BQP와 다항 시간 계층 간의 연결, BQP가 NQP 완성 문제를 포함하는지 여부, BQP 클래스의 정확한 하한 및 상한과 같은 BQP에 대한 질문은 여전히 남아 있다.이러한 질문에 대한 답변은 BQP의 성격을 드러낼 뿐만 아니라 어려운 고전적 복잡성 이론 질문에도 대답할 것이다.BQP를 더 잘 이해하기 위한 전략 중 하나는 관련 클래스를 정의하고 이를 전통적인 클래스 계층 구조로 주문하고 BQP와의 관계에 의해 드러나는 속성을 찾는 것이다.[55]QMA(Quantum Merlin Arthur)와 QIP(Quantum Interactive 다항식 시간)와 같은 몇 가지 다른 양자 복잡성 등급이 있다.[53]

고전적 컴퓨팅으로 할 수 없는 것을 증명하는 어려움은 양자적 우월성을 확실히 증명하는 데 있어 공통적인 문제다.예, 아니오로 대답해야 하는 의사결정 문제와 달리, 표본 추출 문제는 확률 분포에서 표본을 요구한다.[56]임의 양자 회로의 출력에서 효율적으로 샘플링할 수 있는 고전 알고리즘이 있다면 다항식 계층 구조는 3단계로 붕괴될 것이며, 이는 일반적으로 매우 가능성이 낮은 것으로 간주된다.[11][12]보손 표본 추출은 보다 구체적인 제안으로, 고전적 경도는 #P-완전 문제인 복잡한 항목으로 대형 행렬의 영구적 계산의 난해성에 따라 달라진다.[57]이 결론에 도달하기 위해 사용된 주장은 IQP 샘플링으로 확장되었는데,[58] 여기서 문제의 평균과 최악의 복잡성이 같다는 추측만 필요할 뿐 아니라,[56][12] 구글과[38] UTSC 연구그룹에 의해 복제된 과제인 랜덤 회로 샘플링으로도 확장되었다.[42]

제안실험

다음은 흔히 NISQ 장치라고 불리는 현재의 기술을 이용한 양자 계산 패권을 입증하기 위한 제안이다.[2]그러한 제안에는 (1) 잘 정의된 계산 문제, (2) 이 문제를 해결하기 위한 양자 알고리즘, (3) 문제를 해결하기 위한 비교 베스트 케이스 고전 알고리즘, 그리고 (4) 합리적인 가정 하에서 어떤 고전 알고리즘도 현재의 알고리즘보다 현저하게 우수한 성능을 발휘할 수 없다는 복잡성 이론적 주장이 포함된다(그러므로 qua).ntum 알고리즘은 여전히 초항식 속도 증가를 제공한다).[4][59]

Shor의 정수 인수 알고리즘

주요 기사:쇼어 알고리즘

이 알고리즘은 O~({\displaystyle{\tilde{O}}(n^{3})에}time[60]는 반면에 가장 잘 알려 진 고전 알고리즘을 요구한다 2O(n1/3){\displaystyle 2^{O(n^{1/3})}}시간과 최고의 위 이 문제의 복잡성으로 향한다 O(2n/3+o. n비트 정수의 소인수 분해를 찾는다(1 (){\(2(1 또한 홀수 순서의 필드 위에 있는 행렬 그룹의 구성원 문제를 포함하여 정수 인수(factoring)로 감소되는 모든 문제에 대한 속도 업을 제공할 수 있다[61][62]

이 알고리즘은 양자컴퓨팅을 위해 사실상 역사적으로 중요하다.고전 컴퓨터가 어려워하는 실세계 문제에 대해 제안된 최초의 다항식 시간 양자 알고리즘이었다.[60]즉, 오늘날 가장 보편적인 암호화 프로토콜인 RSA가 안전하다는 합리적인 가정 하에 초특급 속도 향상을 제공한다.[63]

팩토링 알고리즘이 난해하게 느린 대규모 사례에서도 팩토링을 정수를 곱하는 것만으로 클래식 컴퓨터로 빠르게 확인할 수 있기 때문에 팩토링은 다른 패권적 제안보다 어느 정도 이점이 있다.다만 쇼르의 알고리즘을 대량으로 구현하는 것은 현재 기술로는 실현 불가능한 것이어서 [64][65]패권을 과시하기 위한 전략으로 추진되지 않고 있다.

보손 표본 추출

주요 기사:보손 표본 추출

선형 광학 네트워크를 통해 동일한 광자를 전송하는 것에 기초한 이 컴퓨팅 패러다임은 몇 가지 복잡성 이론적 추측(가우스 행렬의 영구적 계산이 #P-Hard이고 다항식 계층이 붕괴되지 않는)을 가정할 때 고전적 계산에 난해한 특정 샘플링 및 검색 문제를 해결할 수 있다.ers.[9] 그러나 손실과 소음이 충분히 큰 시스템에서 보손 표본 추출은 효율적으로 시뮬레이션할 수 있는 것으로 나타났다.[66]

현재까지 가장 큰 규모의 보손 샘플링 실험은 6개의 모드를 가지고 있어서 한 번에 최대 6개의 광자를 처리할 수 있었다.[67]보손 샘플링을 시뮬레이션하기 위해 가장 잘 제안된 고전 알고리즘은 광자 및 m 출력 모드가 시스템에 O + m 2 로 실행된다.[68][69]BosonSampling은 R의 오픈소스 구현이다.이 알고리즘은 보손 표본 추출로 양자 우위성을 입증하는 데 필요한 50개의 광자를 추정하게 된다.[68][69]

랜덤 양자 회로의 출력 분포 샘플링

주요 기사:교차엔트로피 벤치마킹

임의 랜덤 양자 회로를 시뮬레이션하기 위해 가장 잘 알려진 알고리즘은 쿼트 수에 따라 기하급수적으로 확장되는 시간을 필요로 하며, 한 집단은 약 50큐빗이 양자 우위성을 입증하기에 충분할 것으로 추정한다.[33]불랜드, 페퍼만, 니르케, 바지라니[12] 등은 2018년 무작위 양자회로를 효율적으로 시뮬레이션하려면 계산 다항식 서열체계의 붕괴가 필요하다는 이론적 증거를 제시했다.구글은 기존 어떤 클래식 컴퓨터에도 접근할 수 없는 분포를 합리적인 시간 안에 샘플링할 수 있는 49Qbit 칩을 구축해 운영해 2017년 말까지 양자 패권주의를 입증하겠다는 뜻을 밝힌 바 있다.[29]당시 클래식 슈퍼컴퓨터에서 작동하던 최대 규모의 범용 양자회로 시뮬레이터는 48큐빗을 시뮬레이션할 수 있었다.[70]그러나 특정 종류의 회로의 경우 56큐빗으로 더 큰 양자 회로 시뮬레이션이 가능하다.[71]이것은 양자 패권을 증명하기 위해 쿼트 수를 증가시켜야 할지도 모른다.[31]구글은 2019년 10월 23일 네이처 기사에서 빠르고 높은 충실도의 양자논리 게이트가 가능한 53qubit 프로세서를 개발한 '프로그래밍 가능한 초전도 프로세서를 이용한 양자 패권주의'라는 양자 패권 실험 결과를 발표했다.구글은 그들의 기계가 200초 만에 목표 연산을 수행했다고 주장하며, 그들의 클래식 알고리즘이 같은 문제를 해결하려면 세계에서 가장 빠른 슈퍼 컴퓨터에서 1만년이 걸릴 것이라고 추정했다.[72]IBM은 개선된 고전 알고리즘이 같은 슈퍼컴퓨터에서 이틀 반 만에 그 문제를 해결할 수 있어야 한다고 말하면서 이 주장에 이의를 제기했다.[73][74][75]

비평

오류에 대한 민감성

양자 컴퓨터는 규율과 소음 때문에 고전적인 컴퓨터보다 오류에 훨씬 더 취약하다.[76]임계값 정리는 소음이 많은 양자 컴퓨터가 양자 오류 수정 코드를[77][78] 사용하여 각 컴퓨터 사이클에 도입된 오류가 일부 숫자보다 작다고 가정할 때 소음 없는 양자 컴퓨터를 시뮬레이션할 수 있다고 명시하고 있다.[79]수치 시뮬레이션을 통해 이 수치가 3%[80]까지 증가할 수 있음을 알 수 있다.그러나 오류 수정에 필요한 자원이 쿼트 수에 따라 어떻게 확장될지는 아직 확실히 알려져 있지 않다.[81]회의론자들은 스케일업된 양자 시스템에서 알 수 없는 소음의 행동을 양자 컴퓨팅을 성공적으로 구현하고 양자 패권을 입증하기 위한 잠재적 장애물로 지적하고 있다.[76][82]

이름 비판

일부 연구자들은 '양적 우월주의'라는 용어가 백인 우월주의라는 인종주의적인 믿음과 혐오스러운 비교를 불러일으킨다고 주장하며 '양적 우월주의'라는 용어를 사용해서는 안 된다고 제안했다.13명의 연구자들이 서명한 논란의[83][84] 네이처 논평은 '양적 우위'라는 대체 문구를 대신 사용해야 한다고 주장한다.[85][86]이 용어를 만든 캘리포니아 공대 이론물리학 교수인 존 프레스킬은 이후 이 용어가 양자 컴퓨터가 결코 고전적인 컴퓨터가 할 수 없는 작업을 수행할 수 있는 능력을 얻는 순간을 명시적으로 설명하기 위해 제안된 것이라고 밝혔다.그는 또한 '양적 우위'라는 용어가 그의 새로운 용어의 의미를 완전히 캡슐화하지 않았기 때문에 특히 거절했다고 설명했다: '양적 우위'라는 단어는 양적 우위성을 가진 컴퓨터가 고전적인 컴퓨터보다 약간 우세할 것이라는 것을 의미할 것이다.자궁.[6] 2020년 12월 네이처의 필립 볼은 '양적 우위'라는 용어가 '양적 우위'[87]라는 용어를 '대부분 대체'했다고 썼다.

참고 항목

참조

  1. ^ a b Preskill, John (2012-03-26). "Quantum computing and the entanglement frontier". arXiv:1203.5813 [quant-ph].
  2. ^ a b c d Preskill, John (2018-08-06). "Quantum Computing in the NISQ era and beyond". Quantum. 2: 79. doi:10.22331/q-2018-08-06-79.
  3. ^ a b Zhong, Han-Sen; Wang, Hui; Deng, Yu-Hao; Chen, Ming-Cheng; Peng, Li-Chao; Luo, Yi-Han; Qin, Jian; Wu, Dian; Ding, Xing; Hu, Yi; Hu, Peng (2020-12-03). "Quantum computational advantage using photons". Science. 370 (6523): 1460–1463. arXiv:2012.01625. Bibcode:2020Sci...370.1460Z. doi:10.1126/science.abe8770. ISSN 0036-8075. PMID 33273064. S2CID 227254333.
  4. ^ a b Harrow, Aram W.; Montanaro, Ashley (September 2017). "Quantum computational supremacy". Nature. 549 (7671): 203–209. arXiv:1809.07442. Bibcode:2017Natur.549..203H. doi:10.1038/nature23458. ISSN 1476-4687. PMID 28905912. S2CID 2514901.
  5. ^ Papageorgiou, Anargyros; Traub, Joseph F. (2013-08-12). "Measures of quantum computing speedup". Physical Review A. 88 (2): 022316. arXiv:1307.7488. Bibcode:2013PhRvA..88b2316P. doi:10.1103/PhysRevA.88.022316. ISSN 1050-2947. S2CID 41867048.
  6. ^ a b c "John Preskill Explains 'Quantum Supremacy'". Quanta Magazine. 2 October 2019. Retrieved 2020-04-21.
  7. ^ Manin, Yu. I. (1980). Vychislimoe i nevychislimoe [Computable and Noncomputable] (in Russian). Sov.Radio. pp. 13–15. Archived from the original on 2013-05-10. Retrieved 2013-03-04.
  8. ^ Feynman, Richard P. (1982-06-01). "Simulating Physics with Computers". International Journal of Theoretical Physics. 21 (6–7): 467–488. Bibcode:1982IJTP...21..467F. CiteSeerX 10.1.1.45.9310. doi:10.1007/BF02650179. ISSN 0020-7748. S2CID 124545445.
  9. ^ a b Aaronson, Scott; Arkhipov, Alex (2011). The Computational Complexity of Linear Optics. Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing. STOC '11. New York, NY, USA: ACM. pp. 333–342. arXiv:1011.3245. doi:10.1145/1993636.1993682. ISBN 9781450306911. S2CID 681637.
  10. ^ King, James; Yarkoni, Sheir; Raymond, Jack; Ozfidan, Isil; King, Andrew D.; Nevisi, Mayssam Mohammadi; Hilton, Jeremy P.; McGeoch, Catherine C. (2017-01-17). "Quantum Annealing amid Local Ruggedness and Global Frustration". arXiv:1701.04579 [quant-ph].
  11. ^ a b Aaronson, Scott; Chen, Lijie (2016-12-18). "Complexity-Theoretic Foundations of Quantum Supremacy Experiments". arXiv:1612.05903 [quant-ph].
  12. ^ a b c d Bouland, Adam; Fefferman, Bill; Nirkhe, Chinmay; Vazirani, Umesh (2018-10-29). "On the complexity and verification of quantum random circuit sampling". Nature Physics. 15 (2): 159–163. arXiv:1803.04402. doi:10.1038/s41567-018-0318-2. ISSN 1745-2473. S2CID 125264133.
  13. ^ Metz, Cade (2019-10-23). "Google Claims a Quantum Breakthrough That Could Change Computing (Published 2019)". The New York Times. ISSN 0362-4331. Retrieved 2020-12-07.
  14. ^ Aaronson, Scott (2019-10-30). "Opinion Why Google's Quantum Supremacy Milestone Matters (Published 2019)". The New York Times. ISSN 0362-4331. Retrieved 2020-12-07.
  15. ^ a b "On "Quantum Supremacy"". IBM Research Blog. 2019-10-22. Retrieved 2019-10-24.
  16. ^ Crane, Leah. "IBM says Google may not have reached quantum supremacy after all". New Scientist. Retrieved 2020-12-07.
  17. ^ Turing, Alan (1936). On Computable Numbers, With An Application To The Entscheidungsproblem.
  18. ^ Benioff, Paul (1980-05-01). "The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines". Journal of Statistical Physics. 22 (5): 563–591. Bibcode:1980JSP....22..563B. doi:10.1007/BF01011339. ISSN 1572-9613. S2CID 122949592.
  19. ^ a b Feynman, Richard P. (1982-06-01). "Simulating physics with computers". International Journal of Theoretical Physics. 21 (6): 467–488. Bibcode:1982IJTP...21..467F. doi:10.1007/BF02650179. ISSN 1572-9575. S2CID 124545445.
  20. ^ "Quantum Computing". Stanford Encyclopedia of Philosophy. September 30, 2019.
  21. ^ Shor, Peter (1996). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.
  22. ^ Monroe, C.; Meekhof, D. M.; King, B. E.; Itano, W. M.; Wineland, D. J. (1995-12-18). "Demonstration of a Fundamental Quantum Logic Gate". Physical Review Letters. 75 (25): 4714–4717. Bibcode:1995PhRvL..75.4714M. doi:10.1103/PhysRevLett.75.4714. ISSN 0031-9007. PMID 10059979.
  23. ^ Grover, Lov K. (1996-11-19). "A fast quantum mechanical algorithm for database search". arXiv:quant-ph/9605043.
  24. ^ Jones, J. A.; Mosca, M. (August 1998). "Implementation of a Quantum Algorithm to Solve Deutsch's Problem on a Nuclear Magnetic Resonance Quantum Computer". The Journal of Chemical Physics. 109 (5): 1648–1653. arXiv:quant-ph/9801027. doi:10.1063/1.476739. ISSN 0021-9606. S2CID 19348964.
  25. ^ Balaganur, Sameer (2019-11-20). "Man's Race To Quantum Supremacy: The Complete Timeline". Analytics India Magazine. Retrieved 2020-11-16.
  26. ^ Merali, Zeeya (June 2011). "First sale for quantum computing". Nature. 474 (7349): 18. Bibcode:2011Natur.474...18M. doi:10.1038/474018a. ISSN 0028-0836. PMID 21637232. S2CID 4425833.
  27. ^ Battersby, Stephen. "Controversial quantum computer beats factoring record". New Scientist. Retrieved 2020-11-16.
  28. ^ Hardy, Quentin (2013-05-16). "Google Buys a Quantum Computer". Bits Blog. Retrieved 2020-11-16.
  29. ^ a b "Google Plans to Demonstrate the Supremacy of Quantum Computing". IEEE Spectrum: Technology, Engineering, and Science News. Retrieved 2018-01-11.
  30. ^ "CES 2018: Intel's 49-Qubit Chip Shoots for Quantum Supremacy". IEEE Spectrum: Technology, Engineering, and Science News. Retrieved 2017-07-22.
  31. ^ a b "Google's quantum computing plans threatened by IBM curveball". October 20, 2017. Retrieved October 22, 2017.
  32. ^ Harris, Mark. "Google has enlisted NASA to help it prove quantum supremacy within months". MIT Technology Review. Retrieved 2018-11-30.
  33. ^ a b Boixo, Sergio; Isakov, Sergei V.; Smelyanskiy, Vadim N.; Babbush, Ryan; Ding, Nan; Jiang, Zhang; Bremner, Michael J.; Martinis, John M.; Neven, Hartmut (23 April 2018). "Characterizing quantum supremacy in near-term devices". Nature Physics. 14 (6): 595–600. arXiv:1608.00263. Bibcode:2018NatPh..14..595B. doi:10.1038/s41567-018-0124-x. S2CID 4167494.
  34. ^ Hartnett, Kevin (June 18, 2019). "A New Law to Describe Quantum Computing's Rise?". Quanta Magazine.
  35. ^ [1], 파이낸셜타임스, 2019년 9월(가입 필요)
  36. ^ "Google touts quantum computing milestone". MarketWatch. Associated Press.
  37. ^ "Demonstrating Quantum Supremacy" – via www.youtube.com.
  38. ^ a b "Quantum Supremacy Using a Programmable Superconducting Processor".
  39. ^ Arute, Frank; et al. (23 October 2019). "Quantum supremacy using a programmable superconducting processor". Nature. 574 (7779): 505–510. arXiv:1910.11333. Bibcode:2019Natur.574..505A. doi:10.1038/s41586-019-1666-5. PMID 31645734.
  40. ^ "What the Google vs. IBM debate over quantum supremacy means ZDNet". www.zdnet.com.
  41. ^ Zialcita, Paolo (23 October 2019). "Google Claims To Achieve Quantum Supremacy — IBM Pushes Back". NPR. Retrieved 2019-10-24.
  42. ^ a b Ball, Philip (2020-12-03). "Physicists in China challenge Google's 'quantum advantage'". Nature. 588 (7838): 380. Bibcode:2020Natur.588..380B. doi:10.1038/d41586-020-03434-7. PMID 33273711.
  43. ^ Garisto, Daniel. "Light-based Quantum Computer Exceeds Fastest Classical Supercomputers". Scientific American. Retrieved 2020-12-07.
  44. ^ Conover, Emily (2020-12-03). "The new light-based quantum computer Jiuzhang has achieved quantum supremacy". Science News. Retrieved 2020-12-07.
  45. ^ Zhong, Han-Sen; Deng, Yu-Hao; Qin, Jian; Wang, Hui; Chen, Ming-Cheng; Peng, Li-Chao; Luo, Yi-Han; Wu, Dian; Gong, Si-Qiu; Su, Hao; Hu, Yi (2021-10-25). "Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light". Physical Review Letters. 127 (18): 180502. arXiv:2106.15534. Bibcode:2021PhRvL.127r0502Z. doi:10.1103/PhysRevLett.127.180502. PMID 34767431. S2CID 235669908.
  46. ^ "Quantum advantage takes a giant leap in optical and superconducting systems". Physics World. 2021-10-26. Retrieved 2021-10-27.
  47. ^ Wu, Yulin; Bao, Wan-Su; Cao, Sirui; Chen, Fusheng; Chen, Ming-Cheng; Chen, Xiawei; Chung, Tung-Hsun; Deng, Hui; Du, Yajie; Fan, Daojin; Gong, Ming (2021-10-25). "Strong Quantum Computational Advantage Using a Superconducting Quantum Processor". Physical Review Letters. 127 (18): 180501. arXiv:2106.14734. Bibcode:2021PhRvL.127r0501W. doi:10.1103/PhysRevLett.127.180501. PMID 34767433. S2CID 235658633.
  48. ^ Zhong, Han-Sen; Deng, Yu-Hao; Qin, Jian; Wang, Hui; Chen, Ming-Cheng; Peng, Li-Chao; Luo, Yi-Han; Wu, Dian; Gong, Si-Qiu; Su, Hao; Hu, Yi; Hu, Peng; Yang, Xiao-Yan; Zhang, Wei-Jun; Li, Hao; Li, Yuxuan; Jiang, Xiao; Gan, Lin; Yang, Guangwen; You, Lixing; Wang, Zhen; Li, Li; Liu, Nai-Le; Renema, Jelmer J.; Lu, Chao-Yang; Pan, Jian-Wei (25 October 2021). "Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light". Physical Review Letters. 127 (18): 180502. arXiv:2106.15534. Bibcode:2021PhRvL.127r0502Z. doi:10.1103/PhysRevLett.127.180502. PMID 34767431. S2CID 235669908.
  49. ^ Sanders, Barry C. (2021-10-25). "Quantum Leap for Quantum Primacy". Physics. 14: 147. Bibcode:2021PhyOJ..14..147S. doi:10.1103/Physics.14.147. S2CID 244826882.
  50. ^ Qingling Zhu, Sirui Cao; et al. (25 October 2021). "Quantum computational advantage via 60-qubit 24-cycle random circuit sampling". Science Bulletin. arXiv:2109.03494. doi:10.1016/j.scib.2021.10.017. ISSN 2095-9273. S2CID 237442167.
  51. ^ Cleve, Richard (2000). "An Introduction to Quantum Complexity Theory" (PDF). CERN. Bibcode:2000qcqi.book..103C.
  52. ^ a b Watrous, John (2009). "Quantum Computational Complexity". In Meyers, Robert A. (ed.). Encyclopedia of Complexity and Systems Science. Springer New York. pp. 7174–7201. doi:10.1007/978-0-387-30440-3_428. ISBN 9780387758886. S2CID 1380135.
  53. ^ a b Watrous, John (April 21, 2018). "Quantum Computational Complexity". arXiv:0804.3401 [quant-ph].
  54. ^ Tereza, Tusarova (2004-09-26). "Quantum Complexity Classes". arXiv:cs/0409051.
  55. ^ Tuˇsarov´a, Tereza (2004). "Quantum complexity classes". arXiv:cs/0409051.
  56. ^ a b Lund, A. P.; Bremner, Michael J.; Ralph, T. C. (2017-04-13). "Quantum sampling problems, BosonSampling and quantum supremacy". NPJ Quantum Information. 3 (1): 15. arXiv:1702.03061. Bibcode:2017npjQI...3...15L. doi:10.1038/s41534-017-0018-2. ISSN 2056-6387. S2CID 54628108.
  57. ^ Gard, Bryan T.; Motes, Keith R.; Olson, Jonathan P.; Rohde, Peter P.; Dowling, Jonathan P. (August 2015). "An introduction to boson-sampling". From Atomic to Mesoscale: the Role of Quantum Coherence in Systems of Various Complexities. World Scientific. pp. 167–192. arXiv:1406.6767. doi:10.1142/9789814678704_0008. ISBN 978-981-4678-70-4. S2CID 55999387.
  58. ^ Bremner, Michael J.; Montanaro, Ashley; Shepherd, Dan J. (2016-08-18). "Average-case complexity versus approximate simulation of commuting quantum computations". Physical Review Letters. 117 (8): 080501. arXiv:1504.07999. Bibcode:2016PhRvL.117h0501B. doi:10.1103/PhysRevLett.117.080501. ISSN 0031-9007. PMID 27588839. S2CID 8590553.
  59. ^ Jordan, Stephen. "Quantum Algorithm Zoo". math.nist.gov. Archived from the original on 2018-04-29. Retrieved 2017-07-29.
  60. ^ a b Shor, P. (1999-01-01). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Review. 41 (2): 303–332. arXiv:quant-ph/9508027. Bibcode:1999SIAMR..41..303S. doi:10.1137/S0036144598347011. ISSN 0036-1445.
  61. ^ Rubinstein, Michael (2006-10-19). "The distribution of solutions to xy = N mod a with an application to factoring integers". arXiv:math/0610612.
  62. ^ Babai, László; Beals, Robert; Seress, Ákos (2009). Polynomial-time Theory of Matrix Groups. Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing. STOC '09. New York, NY, USA: ACM. pp. 55–64. CiteSeerX 10.1.1.674.9429. doi:10.1145/1536414.1536425. ISBN 9781605585062. S2CID 9052772.
  63. ^ Rivest, R. L.; Shamir, A.; Adleman, L. (February 1978). "A Method for Obtaining Digital Signatures and Public-key Cryptosystems". Commun. ACM. 21 (2): 120–126. CiteSeerX 10.1.1.607.2677. doi:10.1145/359340.359342. ISSN 0001-0782. S2CID 2873616.
  64. ^ Martín-López, Enrique; Laing, Anthony; Lawson, Thomas; Alvarez, Roberto; Zhou, Xiao-Qi; O'Brien, Jeremy L. (November 2012). "Experimental realization of Shor's quantum factoring algorithm using qubit recycling". Nature Photonics. 6 (11): 773–776. arXiv:1111.4147. Bibcode:2012NaPho...6..773M. doi:10.1038/nphoton.2012.259. ISSN 1749-4893. S2CID 46546101.
  65. ^ Fowler, Austin G.; Mariantoni, Matteo; Martinis, John M.; Cleland, Andrew N. (2012-09-18). "Surface codes: Towards practical large-scale quantum computation". Physical Review A. 86 (3): 032324. arXiv:1208.0928. Bibcode:2012PhRvA..86c2324F. doi:10.1103/PhysRevA.86.032324. S2CID 119277773.
  66. ^ Rahimi-Keshari, Saleh; Ralph, Timothy C.; Caves, Carlton M. (2016-06-20). "Sufficient Conditions for Efficient Classical Simulation of Quantum Optics". Physical Review X. 6 (2): 021039. arXiv:1511.06526. Bibcode:2016PhRvX...6b1039R. doi:10.1103/PhysRevX.6.021039. S2CID 23490704.
  67. ^ Carolan, Jacques; Harrold, Christopher; Sparrow, Chris; Martín-López, Enrique; Russell, Nicholas J.; Silverstone, Joshua W.; Shadbolt, Peter J.; Matsuda, Nobuyuki; Oguma, Manabu (2015-08-14). "Universal linear optics". Science. 349 (6249): 711–716. arXiv:1505.01182. doi:10.1126/science.aab3642. ISSN 0036-8075. PMID 26160375. S2CID 19067232.
  68. ^ a b Clifford, Peter; Clifford, Raphaël (2017-06-05). "The Classical Complexity of Boson Sampling". arXiv:1706.01260 [cs.DS].
  69. ^ a b Neville, Alex; Sparrow, Chris; Clifford, Raphaël; Johnston, Eric; Birchall, Patrick M.; Montanaro, Ashley; Laing, Anthony (2017-10-02). "No imminent quantum supremacy by boson sampling". Nature Physics. 13 (12): 1153–1157. arXiv:1705.00686. Bibcode:2017arXiv170500686N. doi:10.1038/nphys4270. ISSN 1745-2473.
  70. ^ Hans De Raedt; Fengping Jin; Dennis Willsch; Madita Willsch; Naoki Yoshioka; Nobuyasu Ito; Shengjun Yuan; Kristel Michielsen (November 2018). "Massively parallel quantum computer simulator, eleven years later". Computer Physics Communications. 237: 47–61. doi:10.1016/j.cpc.2018.11.005.
  71. ^ Edwin Pednault; John A. Gunnels; Giacomo Nannicini; Lior Horesh; Thomas Magerlein; Edgar Solomonik; Robert Wisnieff (October 2017). "Breaking the 49-Qubit Barrier in the Simulation of Quantum Circuits". arXiv:1710.05867 [quant-ph].
  72. ^ "Quantum Supremacy Using a Programmable Superconducting Processor". Google AI Blog. Retrieved 2019-11-02.
  73. ^ Metz, Cade (23 October 2019). "Google Claims a Quantum Breakthrough That Could Change Computing". The New York Times. Retrieved 14 January 2020.
  74. ^ Edwin Pednault; John Gunnels; Giacomo Nannicini; Lior Horesh; Robert Wisnieff (October 2019). "Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits". arXiv:1910.09534 [quant-ph].
  75. ^ "Google and IBM Clash Over Quantum Supremacy Claim". Quanta Magazine. 23 October 2019. Retrieved 2020-10-29.
  76. ^ a b Kalai, Gil (2011-06-02). "How Quantum Computers Fail: Quantum Codes, Correlations in Physical Systems, and Noise Accumulation". arXiv:1106.0485 [quant-ph].
  77. ^ Shor, Peter W. (1995-10-01). "Scheme for reducing decoherence in quantum computer memory". Physical Review A. 52 (4): R2493–R2496. Bibcode:1995PhRvA..52.2493S. doi:10.1103/PhysRevA.52.R2493. PMID 9912632.
  78. ^ Steane, A. M. (1996-07-29). "Error Correcting Codes in Quantum Theory". Physical Review Letters. 77 (5): 793–797. Bibcode:1996PhRvL..77..793S. doi:10.1103/PhysRevLett.77.793. PMID 10062908.
  79. ^ Aharonov, Dorit; Ben-Or, Michael (1999-06-30). "Fault-Tolerant Quantum Computation With Constant Error Rate". arXiv:quant-ph/9906129.
  80. ^ Knill, E. (2005-03-03). "Quantum computing with realistically noisy devices". Nature. 434 (7029): 39–44. arXiv:quant-ph/0410199. Bibcode:2005Natur.434...39K. doi:10.1038/nature03350. ISSN 0028-0836. PMID 15744292. S2CID 4420858.
  81. ^ Kalai, Gil (2016-05-03). "The Quantum Computer Puzzle (Expanded Version)". arXiv:1605.00992 [quant-ph].
  82. ^ Dyakonov, M. I. (2007). "Is Fault-Tolerant Quantum Computation Really Possible?". In S. Luryi; J. Xu; A. Zaslavsky (eds.). Future Trends in Microelectronics. Up the Nano Creek. Wiley. pp. 4–18. arXiv:quant-ph/0610117. Bibcode:2006quant.ph.10117D.
  83. ^ Board, The Editorial (17 December 2019). "Opinion Achieving Quantum Wokeness". Wall Street Journal. Retrieved 2019-12-21.
  84. ^ Knapton, Sarah (2019-12-17). "Academics derided for claiming 'quantum supremacy' is a racist and colonialist term". The Telegraph. ISSN 0307-1235. Retrieved 2019-12-21.
  85. ^ Palacios-Berraquero, Carmen; Mueck, Leonie; Persaud, Divya M. (2019-12-10). "Instead of 'supremacy' use 'quantum advantage'". Nature. 576 (7786): 213. doi:10.1038/d41586-019-03781-0. PMID 31822842.
  86. ^ "Open Letter - Responsibility in Quantum Science".
  87. ^ Ball, Philip (17 December 2020). "Physicists in China challenge Google's 'quantum advantage'". Nature. p. 380. doi:10.1038/d41586-020-03434-7. Retrieved 16 December 2020.