Это должна быть экспоненциально сложная задача с одним ответом. То есть количество вариантов ответа растёт с ростом размера входных данных, и из этих вариантов верен только один. Пока по моим данным известны только три задачи такого рода, это
- Поиск простых делителей очень большого числа - ее решение позволит взломать RSA шифры ( о чем мечтает человечество с древности)
- Поиск записи в очень большем словаре по известному одному составляющему пары. Например, вам нужно найти в телефонной книге имя человека по номеру телефона. Имена упорядочены по алфавиту, а номера телефонов с этим упорядочением никак не связаны. Приложение решения этой задачи поиск контекстной рекламы для конкретного человека из огромного словаря (базы данных) «человек- чем интересовался». Очевидно, решение этой задачи черезвычайно важно для выживания человечество.
- Определение минимальной энергии квантовой системы. Гуманитарное приложение: поиск новых лекарств. Современное лекарство это соединение, которое хорошо связывается с ферментом или рецептором (мишенью) в организме и таким образом подавляет (ингибирует) его функционирование. Например средства от давления ингибируют ангеотензин-превращающий фермент. Задачу компьютерного поиска таких соединений решают уже лет 30. Якобы квантовые компьютеры ускорят определение энергии взаимодействия данного соединения с ферментом (рецептором). Однако это не решит задачи, дело в том, что найденное соединение с большой вероятность будет почти невозможно синтезировать. Реально новые лекарства находят среди уже синтезированных соединений путём экспериментального определения его связывания с заданной мишенью. Для этого созданы приборы которые очень быстро это делают с миллионами соединений. Квантовый же компьютер для этих целей будет гораздо сложнее, дороже и нестабильнее чем такие приборы.
Решение задачи создание квантового компьютера конечно развивают науку, но практическая польза от этого весьма призрачна.