
Specifically, Aaronson et al [1]} showed that the problem of identifying whether
\({\Phi _{f_1,\ldots ,f_k}}\le \frac{1}{100}\)  or \(\Phi _{f_1,\ldots ,f_k}\ge \frac{3}{5}\)  has
\(\Omega \left(\frac{2^{\frac{n}{2}}}{n} \right)\)  query complexity in the probabilistic classical model as opposed to
constant query complexity in the bounded error quantum model. To prove those results, they designed the following two quantum algorithms
assuming oracle access to \(f_1\)  through \(f_k\) .

Конкретно, Ааронсон и др. показали [1], что проблема идентификации того, верно ли, что \(\Phi_{f_1,\ldots ,f_k} \le \frac{1}{100}\) или \(\Phi_{f_1,\ldots ,f_k} \ge \frac{3}{5}\), имеет сложность запроса \(\Omega \left(\frac{2^{\frac{n}{2}}}{n} \right)\) в вероятностной классической модели в отличие от постоянной сложности запроса в квантовой модели с ограниченной вероятностью ошибки. Чтобы доказать эти результаты, они разработали следующие два квантовых алгоритма, предполагая наличие оракульного доступа к \(f_1\) через \(f_k\).