부분집합 합

• 영어 명칭: Subset-Sum
• 속도 향상: 다항적
• 구현 코드: ∅

정수의 나열 $x_1,\cdots ,x_n$과 목표 정수 $s$가 주어져 있을 때, 부분집합 합 문제는 주어진 정수 나열의 부분집합 중에서 그것의 합이 $s$가 될 수 있는지를 판정한다. 이 문제는 $\text{NP}$-완전 문제로 최악의 경우에는 고전 알고리즘을 넘어서 양자 알고리즘으로도 다항 시간에 풀 수 없을 수도 있다. 어려운 문제의 경우 주어진 정수들의 크기는 $2^n$에 달하며, 부분집합 합 문제에 관한 많은 연구는 이러한 영역 내에서의 평균 경우 사례들에 초점을 맞춘다. 다항적 인자를 무시한다면, 이러한 문제들을 $2^{0.241n}$의 시간에 해결하는 양자 알고리즘이 [178]에 제시되어 있다. 이 양자 알고리즘은 하우그레이브-그레이엄(Howgrave-Graham)과 주(Joux)가 제안한 정교한 고전 알고리즘을 가속하기 위해, 원소 구별을 위한 암바이니스의 양자 확률보행 알고리즘[7]의 변형을 적용하여 작동한다. 고전 알고리즘 중에서 이를 수행하는 것은 $2^{0.291n}$의 시간에 (다항적 인자 무시) 이를 해결한다 [404].