Алгоритм Дойча-Йожи

Алгоритм Дойча перевершує всі класичні алгоритми для однієї задачі з запитами, але перевага досить скромна: один запит проти двох. Алгоритм Дойча-Йожи розширює цю перевагу — і насправді може застосовуватися для розв'язання кількох різних задач із запитами.

Ось опис алгоритму Дойча-Йожи у вигляді квантової схеми. Залежно від конкретної задачі може також знадобитися додатковий крок класичної постобробки, не показаний на рисунку.

Звісно, ми ще не обговорили, які саме задачі розв'язує цей алгоритм — це розглянуто в двох наступних розділах.

Задача Дойча-Йожи

Розпочнемо з задачі із запитами, для якої алгоритм Дойча-Йожи спочатку й розроблявся, — вона відома як задача Дойча-Йожи.

Вхідна функція цієї задачі має вигляд $f:\Sigma^n \rightarrow \Sigma$ для довільного додатного цілого числа $n.$ Як і в задачі Дойча, завдання полягає в тому, щоб вивести $0$, якщо $f$ константна, і $1$, якщо $f$ збалансована, що знову означає: кількість вхідних рядків, на яких функція приймає значення $0$, дорівнює кількості вхідних рядків, на яких функція приймає значення $1$.

Зауваж, що коли $n$ більше за $1$, існують функції вигляду $f:\Sigma^n \rightarrow \Sigma$, які не є ані константними, ані збалансованими. Наприклад, функція $f:\Sigma^2\rightarrow\Sigma$, визначена як

$$\begin{aligned} f(00) & = 0 \\ f(01) & = 0 \\ f(10) & = 0 \\ f(11) & = 1 \end{aligned}$$

не потрапляє жодну з цих двох категорій. Для задачі Дойча-Йожи ми просто не розглядаємо такі функції — вони вважаються «байдужими» входами. Тобто для цієї задачі є обіцянка, що $f$ або константна, або збалансована.

Задача Дойча-Йожи

Вхід: функція $f:\{0,1\}^n\rightarrow\{0,1\}$
Обіцянка: $f$ або константна, або збалансована
Вихід: $0$, якщо $f$ константна; $1$, якщо $f$ збалансована

Алгоритм Дойча-Йожи з одним запитом розв'язує цю задачу в такому сенсі: якщо всі $n$ результатів вимірювань дорівнюють $0$, то функція $f$ константна; якщо ж хоча б один із результатів вимірювань дорівнює $1$, то функція $f$ збалансована. Інакше кажучи, описана вище схема доповнюється кроком класичної постобробки, в якому обчислюється АБО результатів вимірювань для формування відповіді.

Аналіз алгоритму

Щоб проаналізувати роботу алгоритму Дойча-Йожи для задачі Дойча-Йожи, корисно спочатку розглянути дію одного шару вентилів Адамара. Операцію Адамара можна виразити через матрицю звичним способом:

$$H = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix},$$

але можна також описати цю операцію через її дію на стандартні базисні стани:

$$\begin{aligned} H \vert 0\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} \vert 1 \rangle\\[3mm] H \vert 1\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle - \frac{1}{\sqrt{2}} \vert 1 \rangle. \end{aligned}$$

Ці два рівняння можна об'єднати в одну формулу:

$$H \vert a \rangle = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} (-1)^a \vert 1 \rangle = \frac{1}{\sqrt{2}} \sum_{b\in\{0,1\}} (-1)^{ab} \vert b\rangle,$$

яка справедлива для обох значень $a\in\Sigma.$

Тепер припустимо, що замість одного кубіта маємо $n$ кубітів, і операція Адамара виконується на кожному з них. Загальна операція над $n$ кубітами описується тензорним добутком $H\otimes \cdots \otimes H$ ($n$ разів), який для стислості й чіткості позначаємо $H^{\otimes n}$. Використовуючи наведену вище формулу, а потім розкриваючи й спрощуючи, можемо записати дію цієї комбінованої операції на стандартні базисні стани $n$ кубітів таким чином:

$$\begin{aligned} & H^{\otimes n} \vert x_{n-1} \cdots x_1 x_0 \rangle \\ & \qquad = \bigl(H \vert x_{n-1} \rangle \bigr) \otimes \cdots \otimes \bigl(H \vert x_{0} \rangle \bigr) \\ & \qquad = \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{n-1}\in\Sigma} (-1)^{x_{n-1} y_{n-1}} \vert y_{n-1} \rangle \Biggr) \otimes \cdots \otimes \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{0}\in\Sigma} (-1)^{x_{0} y_{0}} \vert y_{0} \rangle \Biggr) \\ & \qquad = \frac{1}{\sqrt{2^n}} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle. \end{aligned}$$

До речі, тут ми записуємо двійкові рядки довжини $n$ як $x_{n-1}\cdots x_0$ та $y_{n-1}\cdots y_0$, дотримуючись угоди про індексацію в Qiskit.

Ця формула дає нам зручний інструмент для аналізу квантової схеми вище. Після виконання першого шару вентилів Адамара стан $n+1$ кубітів (включно з крайнім лівим / нижнім кубітом, який обробляється окремо) має вигляд

$$\bigl( H \vert 1 \rangle \bigr) \bigl( H^{\otimes n} \vert 0 \cdots 0 \rangle \bigr) = \vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \vert x_{n-1} \cdots x_0 \rangle.$$

Після виконання операції $U_f$ цей стан перетворюється на

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \vert x_{n-1} \cdots x_0 \rangle$$

завдяки точно тому самому явищу фазового відштовхування, яке ми бачили під час аналізу алгоритму Дойча.

Потім виконується другий шар вентилів Адамара, який (за наведеною вище формулою) перетворює цей стан на

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0) + x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle.$$

Цей вираз виглядає дещо складно, і без знання більше про функцію $f$ важко зробити висновки про ймовірності отримання різних результатів вимірювань.

На щастя, все, що нам потрібно знати — це ймовірність того, що всі результати вимірювань дорівнюють $0$, адже саме ця подія означає, що алгоритм визначає $f$ як константну. Ця ймовірність має просту формулу:

$$\Biggl\vert \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \Biggr\vert^2 = \begin{cases} 1 & \text{if $f$ is constant}\\[1mm] 0 & \text{if $f$ is balanced} \end{cases}$$

Детальніше: якщо $f$ константна, то або $f(x_{n-1}\cdots x_0) = 0$ для кожного рядка $x_{n-1}\cdots x_0$ — тоді значення суми дорівнює $2^n$ — або $f(x_{n-1}\cdots x_0) = 1$ для кожного рядка — тоді значення суми дорівнює $-2^n$. Поділивши на $2^n$ і піднісши модуль до квадрату, отримаємо $1$.

З іншого боку, якщо $f$ збалансована, то $f$ приймає значення $0$ на половині рядків $x_{n-1}\cdots x_0$ і значення $1$ на іншій половині, тому члени $+1$ і $-1$ у сумі скорочуються і залишається $0$.

Ми робимо висновок, що алгоритм працює правильно за умови виконання обіцянки.

Складність для класичного алгоритму

Алгоритм Дойча-Йожи працює кожного разу, завжди даючи правильну відповідь, коли обіцянка виконана, і робить лише один запит. Як це порівнюється з класичними алгоритмами із запитами для задачі Дойча-Йожи?

По-перше, будь-який детермінований класичний алгоритм, що правильно розв'язує задачу Дойча-Йожи, повинен робити експоненційно багато запитів: у найгіршому випадку потрібно $2^{n-1} + 1$ запитів. Аргументація така: якщо детермінований алгоритм запитує $f$ на $2^{n-1}$ або менше різних рядках і щоразу отримує однакове значення функції, то обидві відповіді залишаються можливими. Функція може бути константною, або збалансованою, але через невдалий вибір запити випадково повертають однакове значення.

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

Проте є застереження: імовірнісні класичні алгоритми можуть розв'язати задачу Дойча-Йожи з дуже високою ймовірністю, використавши лише кілька запитів. Зокрема, якщо просто вибрати кілька різних рядків довжини $n$ випадковим чином і зробити запит до $f$ на цих рядках, малоймовірно, що ми отримаємо однакове значення функції для всіх них, якщо $f$ збалансована.

Конкретніше: якщо вибрати $k$ вхідних рядків $x^1,\ldots,x^k \in \Sigma^n$ рівномірно випадково, обчислити $f(x^1),\ldots,f(x^k)$, відповісти $0$, якщо всі значення однакові, і $1$ — якщо ні, то ми завжди матимемо правильну відповідь, коли $f$ константна, і помилимося у випадку збалансованої $f$ з імовірністю лише $2^{-k + 1}$. Наприклад, при $k = 11$ цей алгоритм відповідатиме правильно з імовірністю понад $99{,}9$%.

З цієї причини перевага квантових алгоритмів над класичними залишається досить скромною — але вона все ж таки кількісно вимірювана і перевершує перевагу алгоритму Дойча.

Дойч-Йожа з Qiskit

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-aer

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
import numpy as np

Щоб реалізувати алгоритм Дойча-Йожи в Qiskit, почнемо з визначення функції dj_query, яка генерує квантову схему, що реалізує вентиль запиту для випадково вибраної функції, яка задовольняє обіцянку задачі Дойча-Йожи. З імовірністю 50% функція буде константною, а з імовірністю 50% — збалансованою. Для кожної з цих двох можливостей функція вибирається рівномірно з функцій відповідного типу. Аргументом є кількість вхідних бітів функції.

def dj_query(num_qubits):
    # Create a circuit implementing for a query gate for a random function
    # satisfying the promise for the Deutsch-Jozsa problem.

    qc = QuantumCircuit(num_qubits + 1)

    if np.random.randint(0, 2):
        # Flip output qubit with 50% chance
        qc.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance
        return qc

    # Choose half the possible input strings
    on_states = np.random.choice(
        range(2**num_qubits),  # numbers to sample from
        2**num_qubits // 2,  # number of samples
        replace=False,  # makes sure states are only sampled once
    )

    def add_cx(qc, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc.x(qubit)
        return qc

    for state in on_states:
        qc.barrier()  # Barriers are added to help visualize how the functions are created.
        qc = add_cx(qc, f"{state:0b}")
        qc.mcx(list(range(num_qubits)), num_qubits)
        qc = add_cx(qc, f"{state:0b}")

    qc.barrier()

    return qc

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

display(dj_query(3).draw(output="mpl"))

Далі визначимо функцію, яка створює схему Дойча-Йожи, приймаючи як аргумент квантову схему реалізації вентиля запиту.

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in the Deutsch-Jozsa algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)
    qc.h(range(n + 1))
    qc.compose(function, inplace=True)
    qc.h(range(n))
    qc.measure(range(n), range(n))
    return qc

Нарешті, визначимо функцію, яка запускає схему Дойча-Йожи один раз.

def dj_algorithm(function: QuantumCircuit):
    # Determine if a function is constant or balanced.

    qc = compile_circuit(function)

    result = AerSimulator().run(qc, shots=1, memory=True).result()
    measurements = result.get_memory()
    if "1" in measurements[0]:
        return "balanced"
    return "constant"

Перевіримо реалізацію: виберемо функцію випадково, відобразимо квантову схему вентиля запиту для цієї функції, а потім запустимо алгоритм Дойча-Йожи на ній.

f = dj_query(3)
display(f.draw("mpl"))
display(dj_algorithm(f))

'balanced'

Задача Бернштейна-Вазірані

Далі розглянемо задачу, відому як задача Бернштейна-Вазірані. Її також називають задачею вибірки Фур'є, хоча є більш загальні формулювання цієї задачі, що теж мають таку назву.

Спочатку введемо деякі позначення. Для будь-яких двох двійкових рядків $x = x_{n-1} \cdots x_0$ та $y = y_{n-1}\cdots y_0$ довжини $n$ визначимо

$$x \cdot y = x_{n-1} y_{n-1} \oplus \cdots \oplus x_0 y_0.$$

Цю операцію ми будемо називати двійковим скалярним добутком. Альтернативне визначення виглядає так:

$$x \cdot y = \begin{cases} 1 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ is odd}\\[0.5mm] 0 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ is even} \end{cases}$$

Зауваж, що ця операція симетрична: результат не змінюється, якщо поміняти $x$ та $y$ місцями, тому ми можемо це робити, коли зручно. Іноді корисно думати про двійковий скалярний добуток $x \cdot y$ як про паритет бітів $x$ на позиціях, де рядок $y$ має $1$, або еквівалентно — паритет бітів $y$ на позиціях, де рядок $x$ має $1$.

Маючи це позначення, тепер можемо сформулювати задачу Бернштейна-Вазірані.

Задача Бернштейна-Вазірані

Вхід: функція $f:\{0,1\}^n\rightarrow\{0,1\}$
Обіцянка: існує двійковий рядок $s = s_{n-1} \cdots s_0$ такий, що $f(x) = s\cdot x$ для всіх $x\in\Sigma^n$
Вихід: рядок $s$

Насправді нам не потрібен новий квантовий алгоритм для цієї задачі — її розв'язує алгоритм Дойча-Йожи. Для ясності будемо називати квантову схему вище, яка не включає крок класичної постобробки з обчисленням АБО, схемою Дойча-Йожи.

Аналіз алгоритму

Щоб проаналізувати роботу схеми Дойча-Йожи для функції, що задовольняє обіцянку задачі Бернштейна-Вазірані, почнемо з короткого спостереження. Використовуючи двійковий скалярний добуток, можна альтернативно описати дію $n$ вентилів Адамара на стандартні базисні стани $n$ кубітів таким чином:

$$H^{\otimes n} \vert x \rangle = \frac{1}{\sqrt{2^n}} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert y\rangle$$

Подібно до того, що ми бачили під час аналізу алгоритму Дойча, це пояснюється тим, що значення $(-1)^k$ для будь-якого цілого $k$ залежить лише від того, чи $k$ парне, чи непарне.

Повертаючись до схеми Дойча-Йожи: після виконання першого шару вентилів Адамара стан $n+1$ кубітів має вигляд

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} \vert x \rangle.$$

Потім виконується вентиль запиту, який (завдяки явищу фазового відштовхування) перетворює стан на

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} (-1)^{f(x)} \vert x \rangle.$$

Використовуючи нашу формулу для дії шару вентилів Адамара, бачимо, що другий шар Адамарів перетворює цей стан на

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{f(x) + x \cdot y} \vert y \rangle.$$

Тепер можемо зробити деякі спрощення в показнику степеня $-1$ всередині суми. Нам обіцяно, що $f(x) = s\cdot x$ для деякого рядка $s = s_{n-1} \cdots s_0$, тому стан можна записати як

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{s\cdot x + x \cdot y} \vert y \rangle.$$

Оскільки $s\cdot x$ та $x\cdot y$ є двійковими значеннями, можна замінити додавання на виключне АБО — адже для цілого в показнику степеня $-1$ важливо лише, чи воно парне, чи непарне. Скориставшись симетрією двійкового скалярного добутку, отримаємо такий вираз для стану:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\cdot x) \oplus (y \cdot x)} \vert y \rangle.$$

(Для ясності додано дужки, хоча вони формально не потрібні, адже за угодою двійковий скалярний добуток має вищий пріоритет, ніж виключне АБО.)

На цьому кроці скористаємося такою формулою:

$$(s\cdot x) \oplus (y \cdot x) = (s \oplus y) \cdot x$$

Цю формулу можна отримати з аналогічної формули для бітів,

$$(a c) \oplus (b c) = (a \oplus b) c,$$

разом із розкриттям двійкового скалярного добутку та побітового виключного АБО:

$$\begin{aligned} (s\cdot x) \oplus (y \cdot x) & = (s_{n-1} x_{n-1}) \oplus \cdots \oplus (s_{0} x_{0}) \oplus (y_{n-1} x_{n-1}) \oplus \cdots \oplus (y_{0} x_{0}) \\ & = (s_{n-1} \oplus y_{n-1}) x_{n-1} \oplus \cdots \oplus (s_{0} \oplus y_{0}) x_{0} \\ & = (s \oplus y) \cdot x \end{aligned}$$

Це дозволяє записати стан схеми безпосередньо перед вимірюваннями у вигляді:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle.$$

Останній крок — скористатися ще однією формулою, яка справедлива для кожного двійкового рядка $z = z_{n-1}\cdots z_0$:

$$\frac{1}{2^n} \sum_{x \in \Sigma^n} (-1)^{z \cdot x} = \begin{cases} 1 & \text{if $z = 0^n$}\\ 0 & \text{if $z\neq 0^n$} \end{cases}$$

Тут ми використовуємо просте позначення для рядків, яке ще кілька разів зустрінеться в цьому уроці: $0^n$ — це рядок із самих нулів довжини $n$.

Простий спосіб перевірити цю формулу — розглянути два випадки окремо. Якщо $z = 0^n$, то $z\cdot x = 0$ для кожного рядка $x\in\Sigma^n$, тому кожний член суми дорівнює $1$, і при підсумовуванні та діленні на $2^n$ отримаємо $1$. З іншого боку, якщо хоча б один із бітів $z$ дорівнює $1$, то двійковий скалярний добуток $z\cdot x$ дорівнює $0$ рівно для половини можливих $x\in\Sigma^n$ і $1$ для іншої половини — адже значення $z\cdot x$ змінюється (з $0$ на $1$ або з $1$ на $0$) при зміні будь-якого біта $x$ на позиції, де $z$ має $1$.

Застосувавши цю формулу для спрощення стану схеми перед вимірюваннями, отримаємо:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle = \vert - \rangle \otimes \vert s \rangle,$$

оскільки $s\oplus y = 0^n$ тоді й лише тоді, коли $y = s$. Таким чином, вимірювання точно виявляють шуканий рядок $s$.

Складність для класичного алгоритму

Хоча схема Дойча-Йожи розв'язує задачу Бернштейна-Вазірані одним запитом, будь-який класичний алгоритм із запитами повинен зробити щонайменше $n$ запитів.

Це можна обґрунтувати так званим інформаційно-теоретичним аргументом, який у цьому випадку дуже простий. Кожен класичний запит розкриває один біт інформації про розв'язок, а загалом потрібно відкрити $n$ бітів — тому потрібно щонайменше $n$ запитів.

Насправді задачу Бернштейна-Вазірані класично можна розв'язати, запитуючи функцію на кожному з $n$ рядків з одиницею на одній з можливих позицій і нулями на всіх інших, що розкриває біти рядка $s$ по одному. Таким чином, перевага квантового алгоритму над класичним для цієї задачі становить $1$ запит проти $n$ запитів.

Бернштейн-Вазірані з Qiskit

Ми вже реалізували схему Дойча-Йожи вище, і тут скористаємося нею для розв'язання задачі Бернштейна-Вазірані. Спочатку визначимо функцію, яка реалізує вентиль запиту для задачі Бернштейна-Вазірані для будь-якого двійкового рядка $s$.

def bv_query(s):
    # Create a quantum circuit implementing a query gate for the
    # Bernstein-Vazirani problem.

    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc

display(bv_query("1011").draw(output="mpl"))

Тепер можемо створити функцію, яка запускає схему Дойча-Йожи на цій функції, використовуючи функцію compile_circuit, визначену раніше.

def bv_algorithm(function: QuantumCircuit):
    qc = compile_circuit(function)
    result = AerSimulator().run(qc, shots=1, memory=True).result()
    return result.get_memory()[0]

display(bv_algorithm(bv_query("1011")))

'1011'

Зауваження щодо номенклатури

У контексті задачі Бернштейна-Вазірані алгоритм Дойча-Йожи часто називають «алгоритмом Бернштейна-Вазірані». Це дещо вводить в оману, адже алгоритм є алгоритмом Дойча-Йожи, що самі Бернштейн і Вазірані чітко підкреслили у своїй роботі.

Після того як вони довели, що алгоритм Дойча-Йожи розв'язує задачу Бернштейна-Вазірані (у наведеному формулюванні), Бернштейн і Вазірані визначили набагато складнішу задачу — задачу рекурсивної вибірки Фур'є. Це вкрай штучна задача, де розв'язки різних її екземплярів фактично «відкривають» нові рівні задачі, організовані у деревоподібну структуру. Задача Бернштейна-Вазірані — це, по суті, лише базовий випадок цієї складнішої задачі.

Задача рекурсивної вибірки Фур'є стала першим відомим прикладом задачі із запитами, де квантові алгоритми мають так звану надполіноміальну перевагу над імовірнісними алгоритмами, тим самим перевершуючи перевагу квантового алгоритму над класичним, яку демонструє алгоритм Дойча-Йожи. Інтуїтивно кажучи, рекурсивна версія задачі посилює перевагу квантових алгоритмів «$1$ проти $n$» до значно більших значень.

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

Задача Саймона та алгоритм для неї, описані в наступному розділі, дають набагато простіший приклад надполіноміальної (і, власне, експоненційної) переваги квантових алгоритмів над класичними, тому задача рекурсивної вибірки Фур'є рідше обговорюється. Втім, вона залишається цікавою обчислювальною задачею сама по собі.