ШІ довів гіпотезу Ааронсона-Амбайніса: квантові комп'ютери обмежені в задачах без структури

Відредаговано: Svitlana Velhush

Квантовий комп'ютер не зможе експоненційно обігнати звичайний під час розв'язання задач, де вхідні дані майже випадкові й позбавлені особливої математичної структури. Це не просто чергове обмеження — це доведення, отримане штучним інтелектом.

У листопаді 2026 року стартап Physical Superintelligence (PSI) у США оголосив про доведення гіпотези, яку в 2011 році сформулювали Скотт Ааронсон з Техаського університету в Остіні та Андріс Амбайніс з Латвійського університету. Гіпотеза стверджувала: для поліномів низького степеня, що набувають значень від 0 до 1 на булевому кубі, завжди знайдеться змінна з помітним впливом. Доведення знайшла внутрішня дослідницька система PSI на основі непублічної моделі Anthropic. Повний текст пройшов перевірку в системі Lean, а експозицію підготували дослідники Стенфорда — Гай Бланк, Джордан Доктер, Кармен Страссл і Лі-Ян Тан.

Система працювала чотири дні: спочатку отримала повне доведення, потім двічі його покращила, і кожен варіант Lean прийняв без помилок. Це не експеримент на квантовому процесорі, а чисто математичне доведення в галузі теорії складності запитів. Воно показує, що квантовий алгоритм, який робить T запитів до входу, можна з високою точністю змоделювати класично на більшості випадкових входів, використовуючи лише поліноміальне число запитів.

Уявіть величезний склад із мільярдами ящиків, де потрібний предмет лежить у випадковому місці без підказок. Класичний пошук перебирає ящики один за одним. Квантовий міг би, здавалося, зазирнути в усі одразу — але доведення показує, що без особливої структури, як в алгоритмі Шора для факторизації, таке «зазирання» дає лише поліноміальне прискорення, а не експоненційне. Вплив однієї змінної в поліномі гарантує, що випадковий вхід майже завжди можна передбачити за малою кількістю бітів.

Результат змінює уявлення про межі квантової переваги. Тепер ясно: для задач без вбудованої структури — випадкових графів, випадкових функцій — експоненційного виграшу чекати не варто. Квантові комп'ютери зберігають перевагу там, де структура є, як у криптографії чи оптимізації з особливими властивостями. Практичне будівництво пристроїв це не скасовує, але спрямовує зусилля на пошук саме таких структурованих задач.

Стаття в New Scientist від 12 листопада 2026 року та препринт на arXiv від 8 листопада докладно описують хід доведення та його наслідки для співвідношення класів BPP і BQP у світі випадкових оракулів.

Квантова перевага тепер окреслена чіткіше: вона реальна, але потребує не випадковості, а прихованої закономірності.

3 Перегляди

Джерела

  • AI confirms a long-suspected limit on quantum computers’ advantages

  • psi.inc

  • arxiv.org

Коментарі

Знайшли помилку чи неточність?Ми розглянемо ваші коментарі якомога швидше.