Серйозному успіху у квантових обчисленнях завадив підліток

18-річний Ювін Тан довів, що класичні комп’ютери можуть вирішувати «завдання рекомендацій» майже так само швидко, як квантові. Цей результат анулює один з найкращих прикладів квантового прискорення розрахунків.

Підліток з Техасу осадив розвиток квантових обчислень. В опублікованій в цьому місяці в інтернеті роботі 18-річний Ювін Тан довів, що звичайні комп’ютери можуть вирішувати важливу обчислювальну задачу зі швидкістю, потенційно порівнянної з квантовими комп’ютерами.

У найбільш практичному вигляді проблема рекомендацій пов’язана з тим, як сервіси на зразок Amazon і Netflix визначають, які продукти можуть вам сподобатися. Фахівці з інформатики вважали її одним з найкращих прикладів завдань, вирішувати які на квантових комп’ютерах буде експоненціально швидше – що підкреслювало потенційні можливості цих футуристичних машин. І ось тепер Тан спростував цю думку.

«Це був один з визначальних прикладів квантового прискорення – і тепер він зник», — говорить Тан, навесні закінчив навчання в Техаському університеті в Остіні, і початківець цієї осені підготовку до отримання докторського ступеня у Вашингтонському університеті.

В 2014 році, в 14-річному віці, Тан перестрибнув через 4, 5 і 6 класи, і вступив в Техаський університет, де закінчив навчання математики та інформатики. Навесні 2017 Тан пройшов курс квантової інформації, де викладав Скотт Ааронсон, відомий дослідник в області квантових обчислень. Ааронсон розпізнав у Тані незвичайно талановитого студента і запропонував йому стати його радником в незалежному дослідницькому проекті. Ааронсон дав Тану кілька завдань на вибір, включаючи і проблему рекомендацій. Тан обрав її дещо неохоче.

«Я вагався, оскільки вона здавалася досить складною, але це була найпростіша з усіх завдань, які він мені запропонував», — сказав Тан.

Завдання рекомендацій полягає у видачі рекомендацій щодо продуктів, які можуть сподобатися користувачеві. Розглянемо Netflix. Він знає, які фільми ви подивилися. Він знає, що його подивилися мільйони користувачів. Маючи таку інформацію, можна дізнатися, що вам захочеться подивитися далі?

Читайте також  Як купувати на аліекспрес в Україні - Aliexpress

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

У 2016 році фахівці з інформатики Иорданис Керенидис і Анупам Пракаш опублікували квантовий алгоритм, що вирішував завдання рекомендацій експоненціально швидше будь-якого з відомих класичних алгоритмів. Вони отримали таке квантове прискорення, зокрема, завдяки спрощенню завдання. Замість того, щоб заповнювати всю матрицю, і визначати єдиний найкращий продукт для рекомендації, вони придумали спосіб, як можна розбити користувачів на невелику кількість категорій – чи подобаються їм блокбастери або незалежне кіно? – та опрацювати дані так, щоб видати рекомендацію, яка просто була б досить непоганою.

До часу появи роботи Керенидиса і Пракаша існувало дуже мало прикладів завдань, які квантові комп’ютери повинні були вирішувати експоненціально швидше класичних. Здебільшого ці завдання були спеціалізованими – вузькі проблеми, спеціально розроблені для того, щоб користуватися сильними сторонами квантових комп’ютерів (включаючи проблему “форреляции”, про яку ми вже писали). Робота Керенидиса і Пракаша виявилася цікавою тому, що висвітлювала реальну проблему, важливу для людей, в якій квантові комп’ютери обганяли класичні.

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

Керенидис і Пракаш довели, що квантовий комп’ютер може вирішити завдання рекомендацій експоненціально швидше будь-якого з відомих алгоритмів, але вони не довели, що не існує швидкого класичного алгоритму. Тому, коли Ааронсон почав працювати з Таном в 2017 році, він поставив саме таке завдання – довести відсутність швидкого класичного алгоритму, підтвердивши квантове прискорення Керенидиса і Пракаша.

Читайте також  ЯК НАДРУКУВАТИ НЕРОЗРИВНИЙ ПРОБІЛ В MICROSOFT WORD?

«Мені здавалося, що це буде важливою точкою, яку ми поставимо для завершення цієї історії», — сказав Ааронсон, в той час вважав, що швидкого класичного алгоритму не існує.

Тан почав працювати над цим восени 2017 року, розраховуючи, що завдання рекомендацій буде темою його дисертації. Кілька місяців Тан намагався довести неможливість існування класичного алгоритму. Час минав, і Тан почав думати, що, можливо, такий алгоритм все-таки існує.

«Я почав вірити в існування класичного алгоритму, але не міг переконати себе в цьому, оскільки Скотт думав, що його не існує, а він був для мене авторитетом», — сказав Тан.

Нарешті, коли термін здачі дисертації вже підтискав, Тан написав лист Ааронсону, де зізнався у зростаючих у нього підозрах. «Тан написав мені, по суті, таке: Я думаю, що швидкий класичний алгоритм існує», — сказав Ааронсон.

Всю весну Тан записував результати і працював з Ааронсоном над проясненням деяких кроків з доказами. Виявлений Таном швидкий класичний алгоритм був натхненний швидким квантовим алгоритмом, знайденим Керенидисом і Пракашем за два роки до цього. Тан продемонстрував, що квантову вибірку, використану в їх алгоритмі, можна відтворити в класичних умовах. Алгоритм Тана, як і алгоритм Керенидиса і Пракаша, виконувався за полилогарифмическое час – тобто, час обчислень оцінювалося логарифмом від таких параметрів, як кількість користувачів і продуктів – і був експоненціально швидше будь-якого іншого з відомих раніше класичних алгоритмів.

Після завершення Таном алгоритму, Ааронсон хотів переконатися в його правильності перед публікацією. «Я все ще нервував з приводу того, що якщо після публікації Таном роботи вона виявиться невірною, то перша велика робота в кар’єрі Тана виявиться пшиком», — сказав Ааронсон.

Читайте також  Як видалити фото з Фейсбуку

Ааронсон планував відвідати робочу зустріч з квантових обчислень в Каліфорнійському університеті в Берклі в червні. Там повинні були зібратися світила цій області, включаючи і Керенидиса з Пракашем. Ааронсон запросив Тана з собою в Берклі для того, щоб неформально представити його алгоритм після офіційної частини конференції.

Вранці 18 і вранці 19 червня Тан прочитав дві лекції, відповідаючи на запитання аудиторії. По закінченню чотирьох годин був вироблений консенсус: класичний алгоритм Тана схожий на правильний. Чого багато присутні не зрозуміли, так це того, наскільки Тан був юним. «Я не знав, що Ювіну 18 років, і, безумовно, мені так не здалося за результатами розмов. Мені здавалося, що Ювін веде розмову як цілком дорослий чоловік», — сказав Керенидис. Тепер алгоритму належить формальна експертна оцінка перед тим, як його опублікують.

Для квантових обчислень результат Тана служить кроком назад. Чи ні. Тан усунув один з найбільш зрозумілих і кращих прикладів квантової переваги. У той же час, робота Тана є ще одним свідченням наявності плідної взаємодії досліджень класичних і квантових алгоритмів.

«Тан усуває квантове прискорення Керенидиса і Пракаша, але в іншому сенсі Тан сприяє великим поліпшенням і ґрунтується на їх роботі. Тан ніколи б не придумав свій класичний алгоритм, якщо б вони не опублікували свій квантовий», — сказав Ааронсон.

Степан Лютий

Обожнюю технології в сучасному світі. Хоча частенько і замислююся над тим, як далеко вони нас заведуть. Не те, щоб я прям і знаюся на ядрах, пікселях, коллайдерах і інших парсеках. Просто приходжу в захват від того, що може в творчому пориві вигадати людський розум.

You may also like...

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *