부분 결과서지만 확인
Strengths and Weaknesses of Quantum ComputingCharles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani · 1997SIAM Journal on Computing 26(5), 1510–1523쪽 (1997)양자 컴퓨터도 구조를 쓰지 않는 탐색에서는 제곱근만큼의 가속이 한계임을 보인 논문이다. 무작위 오라클에 상대적으로는 양자 컴퓨터도 NP 문제를 2^(n/2) 보다 본질적으로 빨리 풀 수 없음을 보여, 「양자 컴퓨터가 NP-완전 문제를 쉽게 푼다」는 기대에 선을 긋는다. 양자 계산과 P 대 NP 의 관계가 궁금한 독자에게 권한다. arXiv 공개본으로 연결한다.
확인:arXiv 초록 페이지에서 제목·저자·초록을 확인. 본문을 읽었다는 기록은 없음.