숨겨진 부분군 문제

숨겨진 부분군 문제(HSP)는 수학 및 이론 컴퓨터 과학 분야의 연구 주제다.이 프레임워크는 인수, 이산 로그, 그래프 이형성, 최단 벡터 문제와 같은 문제들을 포착한다.이것은 양자컴퓨팅 이론에서 특히 중요한데, 그 이유는 쇼르의 인자화를 위한 양자 알고리즘은 유한 아벨리아 집단의 숨겨진 부분군 문제와 본질적으로 동등하지만, 다른 문제들은 아벨리안이 아닌 유한집단에 해당하기 때문이다.null

문제명세서

그룹 G, 부분군 H ≤ G, 세트 X를 고려할 때, 우리는 함수₁₂ f : G → X는 모든 g, g₁ = G, f(g) = f₁₂(g₂)에 대해 g = gH인 경우에만 부분군 H를 숨긴다고 말한다.동등하게, 함수 f는 H의 코세트에서 상수인 반면, H의 다른 코세츠 간에 상이하다.

숨겨진 부분군 문제:렛츠 G는 그룹이 되고, X는 유한 집합이며, f : G → X는 부분군 H ≤ G를 숨기는 함수. 함수 f는 O(log G +log X ) 비트를 사용하는 오라클을 통해 주어진다.오라클을 통해 f의 평가에서 얻은 정보를 사용하여 H에 대한 생성 세트를 결정한다.

특별한 경우는 X가 그룹이고 f가 그룹 동형인 경우인데, 이 경우 H가 f의 커널에 해당한다.null

동기

숨겨진 부분군 문제는 다음과 같은 이유로 양자컴퓨팅 이론에서 특히 중요하다.null

• 인수 및 이산 로그(그 확장들 중 몇 개뿐 아니라)를 위한 쇼어의 양자 알고리즘은 유한 아벨리아 그룹에 대한 HSP를 푸는 양자 컴퓨터의 능력에 의존한다.
• 특정 비 Abelian 그룹에 대한 HSP를 위한 효율적인 양자 알고리즘이 존재한다는 것은 두 가지 주요 문제, 즉 그래프 이형성 문제와 래티스의 특정 최단 벡터 문제(SVP)에 대한 효율적인 양자 알고리즘을 의미할 것이다.더 정확히 말하면, 대칭 그룹에 대한 HSP를 위한 효율적인 양자 알고리즘은 그래프 이형성에 대한 양자 알고리즘을 제공할 것이다.^[1]다이헤드 그룹의 HSP를 위한 효율적인 양자 알고리즘은 폴리(n) 고유 SVP를 위한 양자 알고리즘을 제공할 것이다.^[2]

알고리즘

유한 아벨리아 그룹에 대한 HSP를 해결하기 위한 다항 시간 양자 알고리즘이 있다.(숨겨진 부분군 문제의 경우, "다항식 시간 알고리즘"은 실행 시간이 그룹 크기의 로그의 다항식인 알고리즘을 의미한다.)쇼어의 알고리즘은 이 양자 알고리즘의 특정한 경우를 적용한다.null

임의 그룹의 경우, 숨겨진 부분군 문제는 오라클의 다항식 평가 횟수를 사용하여 해결할 수 있는 것으로 알려져 있다.^[3]그러나 이 결과는 양자 알고리즘이 로그 G에서 기하급수적인 실행시간을 허용한다. 그래프 이형성과 SVP에 대한 효율적인 알고리즘을 설계하기 위해서는 오라클 평가 횟수와 실행 시간이 모두 다항식인 알고리즘이 필요하다.null

임의 그룹에 대한 그러한 알고리즘의 존재는 개방되어 있다.양자 다항식 시간 알고리즘은 일부 아벨리아 그룹의 반직접 제품과 같은 특정 그룹 하위 클래스에 존재한다.null

The 'standard' approach to this problem involves: the creation of the quantum state ${\displaystyle {\frac {1}{\sqrt { G }}}\sum _{x\in G}{ x\rangle \otimes f(x)\rangle }}$, a subsequent quantum Fourier transform to the left register, after which this register gets sampled.이러한 접근방식은 대칭 그룹의 숨겨진 부분군 문제에 불충분하다는 것이 밝혀졌다.^[4][5]null

참고 항목

• 듀얼 그룹(퀀텀 컴퓨팅)
• 히든 시프트 문제

참조

외부 링크

• Richard Jozsa: 양자 인수, 이산 로그 및 숨겨진 부분군 문제
• 크리스 로몬트:숨겨진 부분군 문제 - 검토 및 개방 문제
• arxiv.org의 숨겨진 부분군 문제