한국의 전력망을 운영하는 기관은 전력거래소다. 전력거래소 자신의 설명에 따르면 하는 일은 두 가지다. 발전사업자와 판매사업자, 대규모 소비자가 참여하는 전력시장에서 매매를 실시간으로 운영하고 감시하는 일, 그리고 수요에 맞춰 발전량을 정하고 안정적으로 공급되게 하는 계통 운영이다. 전력거래소가 매일 하는 일 가운데 하나가 하루전발전계획 수립이다. 거래일의 전력수요를 예측하고 송전망의 제약을 반영해 다음 날 어느 발전기를 어느 시간대에 얼마나 돌릴지 미리 정하고, 그 결과에서 계통한계가격을 산출한다. 계통한계가격은 SMP(System Marginal Price)라고 줄여 쓰며, 그 시간에 수요를 맞추기 위해 마지막으로 투입한 발전기의 발전 단가를 뜻한다. 이 값이 그 시간에 거래되는 전기의 기준 가격이 되므로, 어느 발전기를 켤지 정하는 계획이 곧 가격을 정하는 계획이기도 하다.
계획의 대상은 중앙급전발전기다. 급전이란 어느 발전기가 언제 얼마를 낼지 지시하는 일이고, 중앙급전발전기는 그 지시를 전력거래소로부터 직접 받아 움직이는 발전기를 말한다. 설비용량 20MW를 넘는 발전기가 여기 해당한다. 그 아래 규모나 태양광·풍력 같은 재생에너지 설비는 비중앙급전발전기로 분류되어 개별 지시 없이 발전한 만큼 계통에 들어온다. 전력거래소가 집계한 2024년 12월 31일 기준으로 430대, 설비용량 합계 119,002MW다. 원자력 26대, 석탄 60대, 가스 276대, 수력 55대, 유류 13대로 이루어져 있다. 이 430대를 24시간에 걸쳐 어떻게 배치할지가 하루전발전계획이 답해야 할 물음이다.
하루 전에 미리 정해야 하는 이유는 발전기가 전등 스위치처럼 즉시 켜지지 않기 때문이다. 석탄이나 가스를 태우는 화력 발전기는 정지 상태에서 출력을 낼 수 있는 상태까지 설비를 데우는 데 수 시간이 걸리고, 그동안 연료를 태우면서도 전기는 팔지 못한다. 데우고 식히는 과정에서 금속 부품에 열응력이 쌓여 수명도 줄어든다. 이 두 가지를 합해 기동비용이라고 부른다. 그러니 수요가 잠깐 줄었다고 껐다가 두 시간 뒤에 다시 켜는 식의 운영은 성립하지 않는다. 하루치 수요 곡선을 미리 보고 어느 발전기를 계속 돌리고 어느 발전기를 세워둘지 결정해 두어야 한다.
발전기가 스위치처럼 동작하지 않으므로 계획에는 여러 조건이 붙는다. 한 번 켜면 정해진 시간 이상 돌려야 하고(최소 운전시간), 한 번 끄면 정해진 시간 이상 세워둬야 한다(최소 정지시간). 켜져 있는 동안에도 출력을 0까지 내릴 수 없고 최소출력 아래로는 안정적으로 운전되지 않는다. 학술 논문에 실린 시험계통 자료를 보면 최소출력은 대개 정격의 5분의 1에서 5분의 2 사이다. 한 시간 사이에 출력을 올리고 내릴 수 있는 폭에도 한계가 있다. 보일러와 터빈의 온도를 급격히 바꾸면 설비가 상하기 때문이며, 이 한계를 램프율이라고 부른다. 예컨대 램프율이 시간당 150MW인 발전기는 지금 300MW를 내고 있다면 한 시간 뒤에 450MW까지밖에 올릴 수 없다.
여기에 두 가지가 더 붙는다. 하나는 예비력이다. 전기는 저장해 두고 쓰는 상품이 아니어서 생산과 소비가 매 순간 같아야 하는데, 발전기가 갑자기 고장 나거나 수요 예측이 빗나가면 그 균형이 깨진다. 그래서 수요만큼만 켜 두지 않고 여유분을 함께 확보해 둔다. 다른 하나는 송전선로의 조류 한계다. 조류는 선로에 흐르는 전력을 가리키는 말이고, 선로마다 흘릴 수 있는 최대치가 정해져 있다. 값싼 발전기가 남아 있어도 그 발전소에서 수요지로 가는 선로가 이미 꽉 찼으면 켤 수 없다.
이 문제의 어려움을 설명할 때 관행적으로 등장하는 것이 후보 조합의 개수다. 발전기 N대와 시간 M개면 가능한 배치의 수가 (2N−1)M 규모로 늘어난다. IonQ와 오크리지 국립연구소 연구진이 2025년 발표한 논문은 발전기 15대인 IEEE 9500노드 시험계통을 24시간에 걸쳐 계획할 때 후보 해가 2.3×10108개라고 계산했다. 감각으로 잡히지 않는 수치이니 문제가 감당할 수 없이 어렵게 들린다.
그런데 후보의 개수는 난이도의 척도가 아니다. 앤드루 루카스가 2014년 학술지 Frontiers in Physics에 실은 논문은 이 점을 직접 경고했다. 그는 쉬운 문제도 어려워 보이게 서술할 수 있다고 적으면서, 목록에서 가장 큰 정수를 찾는 문제를 이징 모형으로 쓰면 복잡한 물리 문제처럼 보이지만 실제로는 목록을 한 번 훑으면 끝나는 계산이라는 예를 들었다. 기동정지계획도 마찬가지다. 만약 시간과 시간 사이를 잇는 조건이 하나도 없다면, 24시간짜리 문제는 서로 무관한 24개의 작은 문제로 쪼개지고 각각은 발전기 수백 대 정도로 감당할 만한 크기가 된다.
문제를 실제로 어렵게 만드는 것은 시간을 서로 묶는 조건이다. 3시에 켜기로 하면 최소 운전시간 때문에 6시까지의 선택이 제한된다. 4시에 출력을 크게 올리려면 램프율 때문에 3시의 출력이 이미 어느 수준에 있어야 한다. 기동비용은 지난 시간에서 이번 시간으로 상태가 바뀌었을 때 붙는다. 이번 시간의 상태만 보아서는 계산되지 않는다. 이 조건들이 24개의 시간을 한 덩어리로 만든다. 하루 전체를 동시에 풀어야 하는 이유가 여기 있고, 계산이 어려운 이유도 여기 있다.
고전 컴퓨터에서 이 문제를 푸는 표준 방법은 혼합정수계획(Mixed-Integer Programming)이다. 이름 그대로 정수 값만 갖는 변수와 실수 값을 갖는 변수를 한 모형에 섞어 넣는 방식이며, 켜고 끔이 앞쪽에 출력이 뒤쪽에 해당한다. 여기에 쓰는 탐색 기법이 분지한계법이다. 먼저 이진 변수가 0과 1 사이의 아무 실수나 가질 수 있다고 가정을 풀어 놓고 문제를 푼다. 그러면 계산은 쉬워지지만 발전기를 0.6만큼 켠다는 식의 무의미한 답이 나온다. 대신 조건을 느슨하게 풀었으니 그 답의 비용은 실제 최적해보다 낮고, 그래서 하한선 역할을 한다. 그다음 특정 발전기를 켠 경우와 끈 경우로 문제를 둘로 쪼개고, 각 갈래에서 다시 같은 계산을 한다. 어느 갈래의 하한선이 이미 찾아 둔 해보다 나쁘면 그 갈래는 통째로 버린다. 이 잘라내기 덕분에 모든 조합을 다 뒤지지 않고도 최적해임을 보장할 수 있다. 최악의 경우 계산 시간이 지수적으로 늘어난다는 것은 사실이지만, 실제 성능은 문제를 어떻게 수식으로 적느냐에 크게 좌우된다. 버나드 크누번, 제임스 오스트로프스키, 장폴 왓슨이 2020년 INFORMS Journal on Computing 32권 4호에 실은 논문은 지난 12년간 제안된 기동정지계획 정식화를 전수 검토하고, 기존 요소와 새 요소를 조합해 성능을 크게 개선한 새로운 최고 수준 정식화를 제시했다. 같은 문제, 같은 솔버, 같은 컴퓨터인데 적는 방식만 바꿔 성능이 달라진다는 뜻이다. 양자 쪽이 넘어야 할 기준선은 계속 올라간다.
양자컴퓨터가 이 문제의 후보로 지목된 경로는 명확하다. 켜고 끔이라는 이진 변수가 양자 하드웨어가 다루도록 설계된 형식과 겉모습이 같기 때문이다. 그 형식의 이름이 QUBO다.
루카스의 2014년 논문이 이 통로를 정리한 문헌으로 널리 인용된다. 그는 리처드 카프가 1972년 제시한 21개 NP-완전 문제 전부를 이징 모형으로 옮기는 방법을 제시했고, 각 경우에 필요한 스핀의 수가 문제 크기의 세제곱을 넘지 않는다는 것을 보였다. 여기서 NP-완전이란 답이 주어지면 그것이 맞는지 빠르게 확인할 수 있지만, 답을 처음부터 찾아내는 빠른 방법은 지금까지 발견되지 않은 문제들의 묶음을 가리킨다. 이 묶음에 속한 문제들은 서로 변환이 가능해서, 하나를 빠르게 푸는 방법이 나오면 나머지도 모두 빠르게 풀린다. 반세기 넘게 그런 방법이 나오지 않았고, 존재하지 않는다는 증명도 나오지 않았다. 그래서 루카스가 21개 문제 전부를 이징 모형으로 옮겨 보인 것은 이 묶음 전체로 가는 통로를 열어 둔 작업이 된다.
루카스의 논문에는 이 사상을 실제 장치에 얹을 때 확인해야 할 세 가지도 적혀 있다. 첫째는 필요한 스핀의 수다. 해를 표현하는 데 꼭 필요한 변수 외에 제약을 강제하려고 넣는 보조 변수가 있는데, 그 수가 전체의 대부분을 차지하는 경우가 적지 않다. 둘째는 그래프의 연결 밀도다. 변수끼리 서로 다 연결된 조밀한 문제는 칩 위의 성긴 배선 구조에 얹기가 비효율적이어서, 논리 변수 하나를 여러 물리 소자에 나눠 심고 그것들이 한 몸처럼 움직이도록 강하게 묶어 두어야 한다. 셋째는 결합 상수의 크기 차이다. 제약을 강제하는 벌칙항의 계수가 목적함수 계수보다 문제 크기에 비례해 커져야 하는 경우가 있는데, 장치는 결합 상수를 제한된 정밀도로만 표현한다.
여기서 중요한 대목을 루카스는 이렇게 정리한다. 양자 최적화 장치는 제약이 없는 문제만 풀 수 있으므로, 제약조건은 위반했을 때 에너지가 올라가는 벌칙 해밀토니안으로 바꿔 목적함수 안에 집어넣어야 한다. 제약은 사라지지 않고 목적함수의 일부가 된다. 그러면 계수를 잘못 잡았을 때 제약을 어긴 해가 더 낮은 에너지를 갖게 되고, 하드웨어는 그 해를 정답으로 내놓는다.
여기서 큐비트가 무엇인지 짚어 둘 필요가 있다. 고전 컴퓨터의 비트는 0 아니면 1이다. 큐비트는 측정하기 전까지 0과 1이 함께 섞인 상태에 있을 수 있고 이를 중첩이라고 한다. 다만 측정하는 순간 0이나 1 하나로 정해지므로 두 값을 동시에 읽어 낼 수는 없다. 큐비트의 쓸모는 여러 값을 한꺼번에 담는 데 있지 않고, 계산 중에 각 후보에 붙는 위상을 조절해 오답끼리 서로 상쇄되고 정답 쪽 확률만 커지도록 만드는 데 있다. 큐비트 N개면 2의 N제곱 가지 후보에 대해 이 조작을 한 번에 걸 수 있다.
하드웨어는 두 갈래다. 하나는 양자 어닐링이다. 처음에 모든 배열이 똑같이 가능한 쉬운 계를 만들어 놓고, 그 계를 풀려는 문제의 이징 해밀토니안으로 아주 천천히 바꿔 간다. 충분히 천천히 바꾸면 계가 계속 가장 낮은 에너지 상태에 머무르므로, 다 바꾸고 나서 측정하면 문제의 답이 나온다는 원리다. D-Wave의 장비가 여기 속한다.
다른 하나는 게이트 기반 변분 알고리즘이다. 게이트는 큐비트의 상태를 바꾸는 기본 연산으로 고전 컴퓨터의 논리 게이트에 해당하며, 이것들을 순서대로 늘어놓은 것이 양자회로다. 변분이라는 말은 회로 안에 조절 가능한 손잡이를 여러 개 심어 둔다는 뜻이다. 손잡이를 어떤 값으로 맞춰 회로를 돌리고 결과를 여러 번 측정해 평균 에너지를 구한 다음, 그 값을 고전 컴퓨터의 최적화기에 넘긴다. 최적화기가 손잡이를 조금 돌려 다시 시도하기를 반복해 에너지가 가장 낮아지는 설정을 찾는다. 이 구조를 쓰는 대표적 알고리즘이 QAOA(Quantum Approximate Optimization Algorithm)와 VQE(Variational Quantum Eigensolver)이고, IBM과 IonQ의 장비가 여기 해당한다. 계산의 무거운 반복을 고전 컴퓨터가 맡으므로 양자 쪽 회로를 짧게 유지할 수 있고, 그래서 잡음이 많은 현재 장비에서도 돌릴 수 있다.
기동정지계획을 QUBO로 옮긴 실제 논문들을 열어 보면 공통점이 하나 나온다. 시간을 서로 묶는 제약이 정식화에 없다.
시카고대학교와 커먼웰스 에디슨 등의 연구진이 2021년 IEEE 양자컴퓨팅공학 학술대회에서 발표한 사만다 코레츠키 외의 논문은 QAOA를 기동정지계획에 적용한 초기 연구다. 이 논문은 발전기가 받는 제약으로 최소·최대 출력한계, 램프업과 램프다운 한계, 최소 운전시간과 정지시간, 예비력이 있다고 열거한 다음, 이 논문에서는 최소 출력한계와 최대 출력한계만 다룬다고 밝혔다. 나머지는 모형에서 빠졌다.
2025년 IonQ와 오크리지 국립연구소 연구진이 낸 윌리 아부므라드 외의 논문은 한 걸음 더 나아간다. 이들이 적은 기동정지계획 수식에는 시간별 수급 균형과 출력 상하한만 들어 있고, 기동비용도 최소 운전시간도 램프율도 없다. 논문은 그 결과를 그대로 적었다. 이 문제는 분리 가능하므로 한 시간씩 따로 푼다고 밝혔다. 그래서 이들은 24시간짜리 문제를 24개의 독립된 한 시간짜리 문제로 나눠 풀었고, 그 한 시간짜리 문제를 시간별 기동정지 문제라고 이름 붙였다.
시간이 분리된다는 것은 앞 절에서 본 어려움의 원천이 제거되었다는 뜻이다. 남은 것은 이번 한 시간의 수요를 맞추면서 어느 발전기를 켤지 고르는 문제, 곧 경제급전의 이진 부분이다. 발전기 26대짜리 문제라면 후보는 226개, 약 6,700만 개다. 앞에서 인용한 2.3×10108이라는 수는 24시간을 한 덩어리로 볼 때의 수치이고, 실제로 하드웨어에 얹힌 문제는 그 지수에서 시간 항이 빠진 문제다.
양자 하드웨어가 기동정지계획을 풀었다는 문장은 그래서 두 가지 뜻으로 읽힌다. 전력거래소가 매일 푸는 그 문제를 풀었다는 뜻과, 그 문제에서 이름을 빌려온 축소판을 풀었다는 뜻이다. 지금까지 하드웨어에서 확인된 것은 뒤쪽이다.
제약을 걷어낸 문제에서 양자 쪽 성적은 어느 정도인가. 두 논문이 숫자를 공개했다.
코레츠키 외의 2021년 논문은 IBM의 Qiskit으로 양자회로를 시뮬레이션했고 실제 장비에서는 돌리지 않았다. 발전기 6대, 7대, 8대, 10대짜리 계통을 시험했다. 10대 계통에서 매개변수 최적화를 1,500회 반복한 뒤, 근사 최적해에 해당하는 켜고 끔 조합이 측정될 확률이 회로 깊이 1에서 4퍼센트를 넘었고 깊이 2에서 6퍼센트를 넘었다. 반복 0회에서는 무작위 추측과 다를 바 없던 확률이 올라간 것이니 알고리즘이 작동한다는 근거는 되지만, 한 번 측정해서 정답 근처를 얻을 확률이 스무 번에 한 번이라는 뜻이기도 하다.
아부므라드 외의 2025년 논문은 변분 양자 알고리즘으로 후보 조합을 걸러낸 다음 남은 후보들의 출력을 고전 최적화 루틴으로 정하는 방식을 썼고, 결과를 CPLEX가 구한 최적해와 대조했다. CPLEX는 IBM의 상용 혼합정수계획 솔버다.
결과를 읽으려면 표에 나오는 두 항목을 알아 둬야 한다. 회로 층수는 같은 모양의 게이트 묶음을 몇 번 쌓았는지를 뜻한다. 많이 쌓을수록 회로가 표현할 수 있는 상태의 폭이 넓어져 좋은 답에 닿을 가능성이 커지지만, 조절할 손잡이가 늘어나 최적화에 걸리는 시간이 길어지고 게이트를 지날 때마다 잡음이 더 섞인다. 2큐비트 게이트는 큐비트 두 개를 함께 조작해 서로 얽히게 만드는 연산이며, 큐비트 하나만 건드리는 연산보다 오류율이 한 자릿수 이상 높다. 그래서 양자회로의 부담을 잴 때는 전체 게이트 수보다 2큐비트 게이트의 수를 센다. 시뮬레이션 결과는 아래와 같다.
| 계통 | 회로 층수 | 2큐비트 게이트 | 반복 횟수 | 오차 |
|---|---|---|---|---|
| 발전기 10대 | 1층 | 15 | 59.1 | 1.78% |
| 발전기 10대 | 9층 | 135 | 407.5 | 0.55% |
| 발전기 26대 | 1층 | 57 | 70.7 | 2.74% |
| 발전기 26대 | 9층 | 513 | 487.9 | 2.53% |
게이트 수는 회로에 쓰인 2큐비트 게이트의 개수이고, 반복 횟수는 매개변수 최적화가 수렴할 때까지 걸린 평균 반복 수다. 오차는 CPLEX가 구한 최적해 대비 비용 초과분이며, 24개 시간대와 여러 차례의 독립 시행에 대한 평균이다. 10대 계통은 7회, 26대 계통은 3회 시행했다.
표에서 읽어야 할 것은 두 가지다. 하나는 오차의 크기다. 26대짜리 문제에서 오차 2.5퍼센트는 고전 솔버가 정확한 최적해를 이미 구해 놓은 크기의 문제에서 나온 값이다. 그 최적해가 있었기에 오차를 계산할 수 있었다. 다른 하나는 개선의 기울기다. 회로 층수를 1층에서 9층으로 아홉 배 늘려 게이트 수를 아홉 배 쓰고 반복 횟수를 일곱 배 늘렸는데 26대 계통의 오차는 2.74퍼센트에서 2.53퍼센트로 줄었다. 논문 저자들도 층수를 늘릴수록 개선 폭이 줄어든다고 적었고, 층수와 오차의 관계를 더 이해해야 한다고 남겨 두었다. 같은 논문은 IonQ Forte 장비에서도 일부 시간대를 실행했다. 26대 계통의 24개 시간대를 시뮬레이터와 장비에서 각각 측정한 평균 오차가 3.201퍼센트와 3.088퍼센트로 비슷하게 나왔는데, 이 실행은 매개변수를 고전 시뮬레이션으로 미리 최적화해 두고 그 상태를 장비에서 표본추출만 했다.
양자 우위가 어디서 시작되는지에 대해서는 코레츠키 외의 논문이 직접 답을 적었다. 이들은 CPLEX로 크기를 늘려 가며 고전 성능을 측정한 뒤, 발전기 400대 미만의 기동정지계획 문제에서는 고전 솔버가 충분히 잘 작동하며 양자 우위가 나타나려면 발전기 수백 대 규모의 문제가 필요하다고 결론지었다. 앞에서 본 대로 한국의 중앙급전발전기는 430대다. 양자 우위의 가능성이 시작된다고 이 분야가 스스로 그어 놓은 선이 실계통 규모 바로 아래에 있다. 그리고 그 선은 시간을 묶는 제약을 뺀 문제에 대해 그은 선이다.
제약을 되돌려 놓은 문제를 하드웨어에 얹으려면 큐비트가 몇 개나 필요한가. 계산해 볼 수 있다.
430대를 24시간에 걸쳐 계획하면 켜고 끔을 나타내는 이진 변수만 10,320개다. 기동과 정지가 일어났는지 표시하는 보조 변수를 함께 쓰므로 여기에 두 배가 더 붙는다. 각 발전기의 출력은 연속 변수이므로 QUBO에 넣으려면 이산화해서 이진수로 인코딩해야 하는데, 발전기 하나의 출력 범위를 열여섯 구간으로만 나눠도 4비트가 필요하고 그것만으로 41,280개가 추가된다. 여기에 슬랙 변수가 더해진다. QUBO의 벌칙항은 어떤 값이 정확히 0이 될 때 최소가 되는 형태여서 등식만 다룰 수 있는데, 실제 제약에는 예비력을 얼마 이상 확보하라는 식의 부등식이 많다. 이런 부등식은 남는 만큼을 담아 둘 변수를 하나 새로 만들어 등식으로 바꿔야 하고, 그 변수도 이진수로 인코딩해야 한다. 그 몫이 슬랙 변수다. 논리 큐비트로 10만 개 안팎을 잡아야 하는 규모다.
IBM이 2025년 6월 공개한 로드맵에 두 숫자가 함께 나온다. 이 회사가 2024년 Nature에 발표한 부호는 데이터 큐비트 144개와 검사 큐비트 144개, 합해서 물리 큐비트 288개로 논리 큐비트 12개를 만든다. 논리 큐비트 하나당 물리 큐비트 24개인데, IBM은 이것이 널리 쓰이는 표면부호보다 열 배 적은 수라고 밝혔다. 표면부호는 물리 큐비트를 바둑판처럼 배열하고 이웃끼리만 연결해 오류를 잡는 방식으로, 배선이 단순해 만들기 쉬운 대신 논리 큐비트 하나에 물리 큐비트 수백 개가 드는 것이 약점이다. 그리고 2029년에 가동을 목표로 하는 Starling 시스템의 사양이 논리 큐비트 200개에 게이트 1억 회다. 같은 로드맵에서 그 앞 단계로 제시된 프로세서 Nighthawk는 물리 큐비트 120개에 게이트 5,000회 규모다.
논리 큐비트 200개와 10만 개는 500배 차이다. IBM이 제시한 논리 큐비트당 물리 큐비트 24개를 적용해 환산하면 물리 큐비트로 240만 개가 필요하다는 계산이 나온다. 인코딩을 아무리 아껴도, 예컨대 출력 범위를 같은 폭으로 자르는 대신 낮은 쪽은 촘촘하게 높은 쪽은 성기게 자르는 로그 이산화가 제안되어 있어 같은 비트 수로 더 넓은 범위를 담을 수 있지만, 그런 기법은 변수 수를 몇 분의 일로 줄이는 것이지 세 자릿수를 지우지는 못한다.
규모만 문제가 아니다. 루카스가 적어 둔 세 가지가 기동정지계획 QUBO에 그대로 적용된다. 수급 균형은 그 시간의 모든 발전기를 한꺼번에 묶는 조건이므로 벌칙항을 전개하면 모든 변수 쌍 사이에 결합이 생긴다. 조밀한 그래프이니 칩에 심는 비용이 커진다. 벌칙 계수도 문제다. 아부므라드 외의 논문은 발전기 10대 문제에 벌칙 계수 450,000을, 26대 문제에 700,000을 썼다고 밝혔다. 목적함수의 비용 값이 수만 단위인 것과 비교하면 한 자릿수 이상 큰 값을 계수로 썼다. 양자 장치는 변수 사이의 결합 세기를 아날로그 값으로 걸어 주는데 그 값을 무한한 정밀도로 표현하지 못한다. 큰 값과 작은 값이 한 문제 안에 섞여 있으면 작은 쪽이 장치의 표현 한계 아래로 내려가 무시되고, 그러면 비용을 구분하는 정보가 사라져 제약만 만족하는 아무 해나 나온다.
이 계산을 연구자들이 모르고 있는 것은 아니다. 루이지애나 주립대학교의 밀라드 하산자데, 알리 라자비, 아민 카르가리안이 2026년 1월 공개하고 8월에 개정한 서베이 논문이 이 분야 문헌을 네 갈래로 정리했다. 어닐링 기반, 변분 하이브리드, 양자 기계학습, 양자 영감 메타휴리스틱이다. 이 논문이 남은 한계로 꼽은 항목은 큐비트 수와 잡음과 연결 구조의 제약, 기동정지계획의 제약조건이 만들어 내는 크고 강하게 결합된 QUBO가 현재 장비에 부담이라는 점, 하이브리드 방식에서 양자와 고전 부분 사이의 실행가능성 유지가 어렵다는 점이다. 앞 절에서 계산한 것과 같은 내용이다.
그래서 문헌의 주류는 분해 기반 하이브리드다. 여기 쓰이는 것은 고전 최적화에서 오래전에 자리 잡은 분해 기법들이다. Benders 분해는 이진 결정을 먼저 정하고 그 조건에서 연속 부분을 푼 다음, 그 결과에서 얻은 정보를 이진 쪽으로 되돌려 다음 후보를 좁히기를 반복한다. ADMM(Alternating Direction Method of Multipliers)은 문제를 여러 조각으로 나눠 각각 따로 풀되, 조각들이 공유하는 값이 서로 어긋난 만큼에 가격을 매겨 반복할수록 어긋남이 줄어들게 만든다. 라그랑지안 완화는 지키기 까다로운 제약을 일단 떼어 내고 어겼을 때의 대가를 목적함수에 넣어 푼 뒤, 그 대가의 크기를 조정해 가며 제약을 만족시키는 쪽으로 몰아간다. 어느 쪽이든 하나의 큰 문제를 여러 개의 작은 문제와 그 사이를 오가는 조정 절차로 바꾼다는 점이 같다. 이렇게 쪼갠 뒤, 켜고 끔을 정하는 마스터 문제만 QUBO로 만들어 양자 솔버에 넘기고 출력을 정하는 부문제는 고전 컴퓨터에 남긴다. 지역별로 나눠 작은 QUBO 여러 개를 병렬로 푸는 방식도 같은 계열이다. 아부므라드 외의 논문도 Benders 방식의 분해를 썼고, 양자 부분의 역할을 후보 조합을 걸러내는 체로 규정했다. 이 구조에서 양자가 하는 일은 고전 계산에 넘길 후보 128개까지를 골라 주는 데 그치고, 최종해는 고전 쪽에서 나온다.
서베이가 정리한 네 갈래 가운데 마지막 항목은 성격이 다르므로 구분해야 한다. 양자 영감 메타휴리스틱은 양자유전알고리즘, 양자 입자군집최적화처럼 큐비트 회전 게이트의 수식 형태를 빌려 온 고전 알고리즘이다. 양자 하드웨어를 쓰지 않는다. 서베이도 이 계열이 진정한 양자 가속을 제공하지 않는다고 명시했다. 논문 제목에 양자가 들어 있다는 이유로 같은 묶음으로 읽으면 이 분야의 실제 진척을 크게 부풀려 보게 된다.
이 결과들이 나온 조건도 함께 봐야 한다. 앞에서 인용한 세 편은 모두 발전기 6대에서 26대 사이의 시험계통을 대상으로 했고, 시행 횟수는 계통당 3회에서 7회였으며, 실계통 데이터로 검증한 사례는 없다. 누가 이 연구를 하고 누가 돈을 대는지도 결과를 읽는 데 필요한 정보다. 이 연구들은 모두 시험계통을 대상으로 한 계산 실험이며 표본은 발전기 6대에서 26대 사이, 시행은 계통당 3회에서 7회다. 아부므라드 외의 논문은 저자 다섯 명 가운데 셋이 IonQ 소속이고 둘이 오크리지 국립연구소 소속이며, 미국 에너지부의 전력망 현대화 사업 가운데 GRID-Q 과제의 지원을 받았다. IonQ는 논문이 성능을 보고한 그 장비를 만드는 회사다. 코레츠키 외의 논문은 미국 국립과학재단과 에너지부의 여러 과제 지원을 받았고, 저자 가운데 프레더릭 총이 자신이 양자 스타트업의 수석 과학자이자 다른 양자 기업의 자문임을 논문에 밝혔다. 서베이 논문은 미국 국립과학재단 과제 두 건의 지원을 받았다. IBM의 2029년 사양은 회사가 자사 블로그에 공개한 목표치이며 학술 검증을 거치지 않았다. 이 사실들이 결과를 무효로 만들지는 않는다. 다만 이런 배치에서는 어떤 결과를 논문으로 쓸 만하다고 판단하는 기준이 한쪽으로 기울기 쉽고, 축소된 정식화가 검토 없이 통과되는 것도 그 기울기의 결과일 수 있다.
앞으로 무엇을 보면 판단이 달라지는지는 분명하다. 최소 운전시간과 램프율과 기동비용을 모두 포함한, 즉 24시간이 한 덩어리로 묶인 정식화로 발전기 26대 이상 규모의 결과를 실제 장비에서 보고하는 논문이 나오는지가 첫 번째 지점이다. 지금까지는 시뮬레이터에서든 장비에서든 그런 보고가 없다. 두 번째는 벌칙항 방식을 벗어나는 기법이 기동정지계획에 적용되는지다. 벌칙항은 제약을 어긴 해도 일단 후보로 두고 점수만 깎는 방식이라 계수를 잘못 잡으면 실행 불가능한 해가 정답으로 나온다. 대안은 회로 자체를 제약을 만족하는 상태들 사이에서만 움직이도록 설계해 애초에 위반 상태로 넘어가지 못하게 하는 것이며, 그 역할을 하는 부분을 제약 보존 믹서라고 부른다. 세 번째는 대조군이다. 같은 시간 예산 아래 상용 혼합정수계획 솔버와 표준 시험계통에서 맞붙인 결과가 나오는지를 보면 된다. 이 세 가지가 확인되지 않는 한, IBM의 2029년 목표가 예정대로 달성되더라도 실계통 기동정지계획을 양자가 대체하는 그림은 성립하지 않는다. 반대로 이 판단이 틀렸다고 볼 근거는 인코딩 효율이 세 자릿수 단위로 개선되거나, 오류정정 오버헤드가 논리 큐비트당 물리 큐비트 한 자릿수로 떨어지거나, 분해 기법이 실계통 규모 문제를 현행 장비에 얹히는 크기의 부문제로 쪼개면서도 전체 최적성을 잃지 않는다는 것이 입증되는 경우다.
발전기 기동정지계획은 양자 최적화의 대표적 후보 문제로 꼽히고, QUBO라는 사상 경로도 분명하며, 국제 학술지와 학회에 매년 논문이 쌓이고 있다. 그러나 이 문제를 어렵게 만드는 것은 24시간을 한 덩어리로 묶는 제약과 연속 출력변수다. 켜고 끔이라는 이진 결정만 놓고 보면 규모가 훨씬 작아진다. 양자 하드웨어가 요구하는 QUBO 형식은 바로 그 두 가지를 감당하지 못한다. 제약은 벌칙항이 되어 목적함수로 들어가고, 연속 변수는 이산화되어 변수 수를 늘린다. 그래서 하드웨어에서 실제로 풀린 사례들은 시간을 묶는 제약을 빼고 남긴 축소판이었다. 코레츠키 외의 2021년 논문은 출력 상하한만 다룬다고 밝혔고, 아부므라드 외의 2025년 논문은 문제가 시간별로 분리된다고 적은 뒤 24개의 독립된 한 시간짜리 문제로 나눠 풀었다.
그 축소판에서 나온 성적도 고전 솔버를 대체할 수준이 아니다. 발전기 26대 문제에서 CPLEX 최적해 대비 오차가 2.5퍼센트대이고, 회로를 아홉 배 깊게 만들어도 오차가 거의 줄지 않았다. 양자 우위가 나타나려면 발전기 수백 대 규모가 필요하다는 것은 이 분야 논문이 스스로 계산해 적어 놓은 결론이며, 한국의 중앙급전발전기 430대는 그 선 위에 있다. 규모를 맞추려면 논리 큐비트가 10만 개 안팎 필요한데 IBM이 2029년 목표로 내건 값은 200개다. 한편 비교 대상인 고전 쪽은 정지해 있지 않다. 크누번 외의 2020년 논문이 보여준 것처럼 같은 문제를 어떻게 적느냐만으로도 혼합정수계획의 성능은 크게 달라진다.
정리하면 판단은 무엇을 이 문제의 본체로 보느냐에 달려 있다. 이진 조합 탐색을 본체로 보면 기동정지계획은 양자에 잘 맞는 문제이고 지금까지의 결과는 순조로운 초기 단계다. 시간축 제약을 본체로 보면 이 분야는 아직 그 본체에 손을 대지 못했고, 지금까지의 결과는 다른 문제에 대한 결과다. 후자가 전력계통 운영자가 쓰는 정의이며, 그 정의를 기준으로 삼으면 진척 정도는 초기 단계라기보다 착수 이전에 가깝다.
남는 물음은 이 격차가 하드웨어의 성장으로 메워질 성질인지, 아니면 정식화 자체를 다시 짜야 하는 문제인지다. 지금 문헌이 향하는 방향은 후자에 가깝다. 구조 인지형 QUBO, 분산 양자 구조, 제약 보존 믹서는 모두 하드웨어가 커지기를 기다리는 대신 문제를 하드웨어 쪽으로 다시 적어 보려는 시도다. 그렇다면 판별의 시점은 특정 논문이 나오는 때다. 최소 운전시간과 램프율을 되돌려 놓은 정식화로 실제 장비에서 결과를 보고하고, 같은 시간 예산의 상용 솔버와 나란히 놓은 논문 말이다. 그런 논문이 나오기 전까지 기동정지계획은 양자컴퓨팅의 유망 응용 목록에 이름이 올라 있는 문제이지, 양자로 풀린 문제가 아니다.