캘리포니아주 서니베일 – 26년 2022월 XNUMX일 – NTT Research는 암호화 및 정보 보안(CIS) 연구실 그리고 에서 온 동료 NTT 사회 정보학 연구소 (SIL)은 양자 이점에 대한 획기적인 논문을 작성했습니다. 이 논문은 31월 3일부터 XNUMX월 XNUMX일까지 열리는 IEEE FOCS(Computer Science Foundations of Foundations) 연례 심포지엄에서 발표될 예정입니다. XNUMX위 덴버.
"라는 제목의 논문의 공동 저자구조 없이 검증 가능한 양자 이점,” NTT SIL의 저명한 연구원인 Takashi Yamakawa 박사와 Dr. Mark Zhandry의 선임 과학자입니다. NTT 리서치 CIS 연구소 이 작업은 야마카와 박사가 방문 연구 학자였으며 Zhandry 박사가 컴퓨터 과학 조교수로 재직 중인 Princeton University에서 부분적으로 수행되었습니다.
양자 이점(또는 양자 속도 향상)의 주제는 양자 컴퓨터가 고전적 또는 비양자 컴퓨터보다 더 빨리 해결할 수 있는 문제의 종류와 그 속도가 얼마나 빠른지에 관한 것입니다. 문제의 문제는 일반적으로 비결정적 다항식 시간(NP) 클래스로 설명됩니다. 얼마나 많은 이점이 광대한 정도로 달라질 수 있습니다. 양자 컴퓨터는 고전적인 컴퓨터가 일주일이 걸리는 특정 문제를 XNUMX분 또는 XNUMX초 만에 해결할 수 있으며, 아마도 헤아릴 수 없을 정도로 기하급수적인 시간이 소요될 수도 있습니다. 이 백서에서 저자는 이러한 우월성을 검증하고 효율적으로 수행하는 문제를 해결합니다. 현재까지 양자 이점의 시연은 중요한 "구조" 또는 둘 이상의 당사자 간의 양방향 통신과 관련되었습니다. Yamakawa와 Zhandry 논문의 돌파구는 구조 없이 검증이 가능한 NP 하드 문제를 입증하는 것입니다.
"임의의 오라클만 필요한 NP 검색 문제에 대한 기하급수적인 양자 속도 향상을 본 것은 이번이 처음입니다."라고 초기 버전에 대해 논평한 텍사스 대학 오스틴 교수 컴퓨터 과학 교수 Scott Aaronson이 말했습니다. 13년 2022월 XNUMX일 Simons Institute for Theory of Computing에서 열린 워크숍에서 논문의 내용입니다. 임의의 오라클, 즉 각 쿼리에 대해 임의의 응답을 생성하는 이론적 블랙박스만 요구함으로써 Yamakawa와 Zhandry는 구조화되지 않은 계산 가정에 대한 문제를 구축했습니다. 따라서 그들의 문제는 공개 키 암호화에서 발견되는 것과 같은 구조화된 기능 대신 단방향 기능과 더 밀접하게 일치합니다. 이러한 단방향 정렬은 효율적인 검증을 용이하게 합니다.
고미 카즈히로(Kazuhiro Gomi)는 "특히 NTT 리서치의 또 다른 초점인 양자 컴퓨팅에 대한 이해를 강화하는 논문에서 '혁신'이라는 레이블을 다시 한 번 가치가 있는 연구에 NTT 관련 암호학자들이 협력하는 것을 보는 것은 흥미진진합니다."라고 말했습니다. , NTT 리서치 사장 겸 CEO. “이 권위 있는 IEEE 컨퍼런스에 참석한 모든 참가자들에게 축하와 행운을 빕니다.”
Yamakawa와 Zhandry가 고안한 NP 탐색 문제는 1) 주어진 오류 수정 코드의 코드 워드인 n-기호 문자열과 2) 기호는 임의의 오라클에서 XNUMX으로 매핑됩니다. 각 문제는 개별적으로 쉽습니다. 그러나 코드워드이면서 XNUMX에 매핑되는 단일 기호 문자열을 찾는 것은 적어도 고전적으로는 훨씬 더 어렵습니다. Zhandry 박사는 “만약 당신이 양자라면 이것을 다항식 시간 안에 풀 수 있습니다. 그러나 당신이 고전적이라면 최소한 이 블랙박스 모델에 있다면 기하급수적인 시간이 필요합니다.”라고 말했습니다. 반면에 잠재적인 솔루션이 주어지면 두 가지 문제를 각각 별도로 해결하는지 확인하여 간단하게 검증할 수 있습니다. FOCS에 대한 논문에 적합하므로 이 작업은 기본 또는 기초입니다. Simons Institute에서 Aaronson 박사의 연설에서 지적한 바와 같이(이 NTT 연구에서 논의됨) 블로그 기사), Yamakawa-Zhandry 인수는 수학적으로 쉽게 확인할 수 있는 속도 향상의 클래스에 속하지만 실제 양자 컴퓨터에서는 조만간 실제로 시연되지 않습니다. 그러나 획기적인 검증 계획 외에도 이 논문은 양자 속도 향상의 범위와 관련하여 새로운 점을 지적합니다.
“우리 작업에 앞서 인수분해 또는 블랙박스 설정에서 기간 찾기와 같은 NP 문제에 대한 양자 이점의 예가 있었습니다. 그러나 이러한 모든 예의 기초가 되는 양자 알고리즘은 기본적으로 기간 찾기인 것으로 밝혀졌습니다. 그러나 이러한 예에 기간 찾기를 적용하는 방법을 보여주는 것은 종종 사소하지 않은 경우가 많았습니다.”라고 Zhandry 박사가 말했습니다. “우리 신문은 적어도 두 번째 사례가 있음을 보여줍니다. 양자 이점이 이전에 생각했던 것보다 더 널리 퍼져 있다는 희망이 있다고 낙관적으로 해석할 수 있습니다.”
IEEE Computer Society Technical Committee on Mathematical Foundations of Computing(TCMF)이 후원하는 FOCS는 이론적인 컴퓨터 과학 분야의 선도적인 컨퍼런스입니다. 2022회째를 맞는 FOCS 63에 대한 논문 공모에서는 양자 컴퓨팅을 17개의 일반적인 관심 분야 중 하나로 나열했습니다. Yamakawa-Zhandry 논문은 31년 2022월 10일 오전 15시 XNUMX분(MT)에 발표될 예정입니다. 이 이벤트에 대해 자세히 알아보고 등록하려면 다음을 방문하세요. FOCS 2022 웹 사이트를 방문 하십시오.
