데이터 베이스 검색용 새로운 양자 알고리즘

중앙일보

입력

Lucent Technologies의 연구부문인 Bell Labs의 연구원이, 양자 컴퓨터를 사용하면 대규모 데이터베이스에서 많은 검색 조건을 붙여도 결과를 찾아내는 것이 가능한 새로운 양자 알고리즘을 발견했다.

발견한 사람은 Lov Grover로, 이 연구 결과는 이번 주에 열리는 학회 「ACM STOC」에서 발표된다.

양자 컴퓨터란 마이크로 세계의 양자 역학적인 효과를 이용해 초병렬적인 계산을 행하기 위한 새로운 계산의 범위이다. 현재, 실생활에 사용할 수 있는 양자 컴퓨터는 실현되어 있지 않으며, 많은 과학자가 실현을 향해 연구를 하고 있다.

이 양자 컴퓨터로 실현된 새로운 알고리즘을 사용하면, 거의 잊어 버리고 있었던 정보도 많은 검색 조건을 사용해 찾아내는 것이 가능하다. Glover씨는, 잊고 있던 사람의 이름을 검색하는 것을 예로 들어 다음과 같이 말한다.

「예를 들면 그사람의 성이 John이였던 것은 기억하고 있어도 이름을 기억할 수 없을 때에, 확실히 그 이름이 Smith라든가 Jones이나 Miller같은지 보통의 이름이었던 것은 기억하고 있다고 하자. 그 때에, 그 이름이 Smith일 가능성이 50%, Jones일 가능성이30%, Miller일 가능성이 20%라고 하자.

당신은 그가 뉴욕시의 Licoln Center의 근처에 살고 있고 Broadway가 잘 보이는 아파트에 살고 있던 것을 기억하고 있다고 하자. 그리고, 그의 전화 번호의 마지막 4자리수가 자신의 의사의 번호와 같았던 것을 기억해냈다고 하자.

전화번호부를 보고 뉴욕시에 살고 있는 모든 John Smith (혹은 Jones, Miller) 를 재빠르고 정확하게 찾아내는 기존의 방법은 없다. 그러나, 나의 새로운 알고리즘과 양자 컴퓨터가 있으면 이러한 검색도 가능하게 되는 것이다.」

Grover는 이전에도 데이터베이스 검색을 위한 양자 알고리즘을 발견했었고, 이 결과는 널리 알려져 있다.

이 알고리즘을 사용하면 지금까지 몇 백만개의 데이터가 들어 있는 대규모 데이타베이스에서 아이템을 찾아내는데 기존의 방법으로는 평균 50만 스텝이 필요했던 것이, 단지 1,000스텝만으로 끝낼 수 있다. 이 알고리즘은 2년전에 극히 원시적인 형식의 양자 컴퓨터의 원형에서 확인되었다.

이와 같이 양자 컴퓨터의 잠재적가능성은 크다. 하지만, Bell Labs의 Richart Slusher는 「아직 그저 조금의 양자 알고리즘밖에 존재하지 않는다. 이것들은 발명하는 것이 매우 어렵고, 아직 이 분야의 역사가 짧기 때문이다」라고 연구의 어려움을 지적한다.