Хотя экспоненциальное разделение между сложностью квантового запроса с ограниченной ошибкой ( ) и сложностью детерминированного запроса ( ) или сложностью рандомизированного запроса с ограниченной ошибкой ( ) известно, они применяются только к определенным частичным функциям. Если частичные функции имеют некоторые специальные структуры, то они также полиномиально связаны с . Тем не менее, меня больше всего волнуют общие функции.
В классической работе было показано, что ограничена для полных функций, для монотонных полных функций и для симметричные полные функции. Однако для такого рода функций известно не более квадратичного разделения (это разделение достигается например). Насколько я понимаю, большинство людей предполагают, что для полных функций мы имеем . При каких условиях эта гипотеза была доказана (кроме симметричных функций)? Каковы наилучшие текущие оценки сложности дерева решений с точки зрения сложности квантовых запросов для полных функций?
источник