고전적인 선형 대수 솔버가 비슷한 속도 향상으로 양자 알고리즘을 구현할 수 있습니까?
양자 알고리즘은 초기 상태의 큐 비트 레지스터로 시작하고 단위 연산자 (알고리즘)가 해당 큐 비트의 상태를 조작 한 다음 큐 비트의 상태를 읽습니다 (또는 하나의 상태에 대한 최소한 일부 정보). 알고리즘 실행).
양자 컴퓨터가 양자 상태에 대한 단일 행위의 질문에 답하는 것 같습니다. 이것은 선형 대수의 문제입니다. 그렇다면 양자 컴퓨터가 선형 대수 계산기로 보일 수 있다는 사실이 저를 놀라게합니다.
그렇다면 양자 역학이 필요한 이유는 무엇입니까? 선형 대수 연산을 구현하는 고전적인 시스템을 찾을 수없고이를 사용하여 양자 컴퓨터 용으로 설계된 알고리즘을 구현할 수 없습니까? 물론 고전적인 디지털 컴퓨터로는 충분하지 않을 것입니다. 이러한 기계는 고차원 공간에서 벡터를 조작하는 것이 아니라 정보의 이진 처리를 기반으로합니다.
질문 : "양자 컴퓨터"알고리즘을 구현하면서 디지털 클래식 컴퓨터에 비해 유사한 속도 향상을 즐길 수있는 클래식 선형 대수 솔버 (고전 아날로그 컴퓨터)에 대한 후보가 있습니까?
질문 2 : 아마도 저는 양자 컴퓨터를 단순한 선형 대수 솔버로 줄임으로써 지나치게 단순화하고있을 것입니다. 이것이 사실입니까? 나는 어떤 복잡성을 감추고 있습니까?
답변
당신이 설명하는 복잡성은 일반적인 경우에 저장해야한다는 것입니다. $2^n$ 복잡한 진폭은 $n$큐 비트 시스템은 고전적으로. 따라서 1000 큐 비트의 양자 컴퓨터의 경우 저장해야합니다.$2^{1000}$복잡한 진폭. 이를 위해 진폭 당 하나의 원자를 사용하더라도 관측 가능한 우주에서는 여전히 원자가 부족합니다.
내가 아는 한, 위는 일반적인 주장입니다. 그러나 알고리즘의 표현 요구 사항을 절약하기 위해 영리한 통찰력을 활용하여 고전적으로 다루기 쉬운 방식으로 특정 양자 알고리즘을 표현하는 방법이 여전히있을 수 있습니다.$2^n$요구 사항. 그러나 이것은 특정 문제 일 가능성이 높으며 일반적인 경우에는 작동하지 않을 수 있습니다.
디지털 대 아날로그 계산에 관한 질문의 진술에 따라이 사이트에는 유사한 제안에 대해 문의 한 다른 스레드가 있습니다. 예를 들어 여기 및 여기를 참조 하십시오 . 무엇보다도 고전적인 아날로그 시스템은 얽히게 할 수 없습니다. 따라서 양자 컴퓨터를 아날로그 컴퓨터로 다시 캐스팅하는 것은 관찰 된 속도 향상으로 이어지지 않습니다.
그럼에도 불구하고 @Attila Kun의 답변에 더 나아가 선형 대수 / 머신 러닝에는 빠른 양자 알고리즘을 사용했지만 비슷한 속도 향상을 가진 고전 알고리즘으로 다시 캐스팅 된 특정 문제가 있습니다.
예를 들어 Netflix / Amazon 등에서 사용 하는 추천 문제 입니다. 양자 컴퓨터에서 빠른 알고리즘을 가지고 있습니다. 이 알고리즘은 (당시) 가장 잘 알려진 고전 알고리즘에 비해 기하 급수적으로 향상되었습니다.
그러나 양자 알고리즘이 정말로 우수하다는 것을 증명하기 위해 E. Tang은 실제로 "선형 대수 연산을 구현하고이를 양자 컴퓨터 용으로 설계된 알고리즘을 구현하는 데 사용하는 고전적인 시스템"이 있음을 보여주었습니다.
Tang의 작업은 역 양자화 프로그램을 시작했습니다. 즉, 선형 대수 / 기계 학습에서 고속 양자 알고리즘을 빠른 고전 알고리즘으로 재 설계하는 것입니다. Quanta Magazine 기사 는 문제와 Tang의 접근 방식을 설명합니다.
이 스레드가 논의하는 것처럼 이 역 양자화에 어떤 문제가 해결 될 수 있는지는 활발한 연구 영역입니다 . 이것은 고려되는 행렬의 순위에 따라 달라질 수 있습니다.