Формула для определения типа функции с использованием кубитов:
f(x) = H^n-1(x)⊗{0,1} + C(1 - H^n-1(x)⊗{0,1})
где H^n-1(x) обозначает применение операции Адамара (Hadamard) ко всем кубитам, кроме последнего (n-1); ⊗ - означает тензорное произведение (произведение Кронекера); {0,1} - вектор состояния последнего кубита (например, {0} для константной функции и {1} для сбалансированной); C - оператор контролирующего изменения фазы, который применяется только в случае, если последний кубит имеет состояние {1}.
Таким образом, если мы измеряем все кубиты кроме последнего и получаем значениe {0}, то функция будет константной, а если мы получаем значениe {1}, то функция будет сбалансированной. Эта формула позволяет быстро и точно определять тип функции, используя только один квантовый алгоритм.
Перевод на математический язык:
H^n-1(x) - операция Адамара (Hadamard transform), применяемая ко всем кубитам, кроме последнего (n-1). Это можно записать как
H^n-1(x) = H(x_1)⊗H(x_2)⊗...⊗H(x_n-1),
где H(x_i) - операция Адамара, применяемая к i-му кубиту, а ⊗ - тензорное произведение.
{0,1} - вектор состояния последнего кубита, который можно записать как
{0,1} = |0⟩ ⊗ |1⟩,
где |0⟩ и |1⟩ - базисные кеты кубита.
C - оператор контролирующего изменения фазы, который применяется только в случае, если последний кубит имеет состояние {1}. Это можно записать как
C = |1⟩⟨1|,
где |1⟩⟨1| - проекционный оператор на кет-состояние |1⟩.
Итак, полный расклад формулы для определения типа функции f(x) с использованием кубитов выглядит следующим образом:
f(x) = H^n-1(x)(|0⟩ ⊗ |1⟩) + C(1 - H^n-1(x)(|0⟩ ⊗ |1⟩))
= (H(x_1)⊗H(x_2)⊗...⊗H(x_n-1))(|0⟩ ⊗ |1⟩) + |1⟩⟨1|(1 - (H(x_1)⊗H(x_2)⊗...⊗H(x_n-1))(|0⟩ ⊗ |1⟩))
= (H(x_1)|0⟩ ⊗ H(x_2)|0⟩ ⊗ ... ⊗ H(x_n-1)|0⟩ ⊗ |1⟩) + |1⟩⟨1|(1 - H(x_1)|0⟩ ⊗ H(x_2)|0⟩ ⊗ ... ⊗ H(x_n-1)|0⟩ ⊗ |1⟩)
= 1/2^(n/2)∑(x,y) f(x)(-1)^(x⋅y)|x⟩(|0⟩ - (-1)^{f(x)⋅y}|1⟩),
где x = (x_1,x_2,...,x_n-1) - битовая строка переменных, y - битовая строка из {0,1}, x⋅y - скалярное произведение двух битовых строк (берутся по модулю 2), |x⟩ - базисный кет состояния для битовой строки x. Эта формула представляет функцию f(x) в виде суперпозиции базисных кетов, где каждый кет соответствует комбинации переменных и состояний последнего кубита, а коэффициенты перед кетами определяются значением функции f(x).
Таким образом, мы можем получить тип функции, применив операцию Адамара ко всем кубитам, измерив все кубиты кроме последнего и анализируя состояние последнего кубита. Если мы получаем состояние |0⟩, то функция константная, а если мы получаем состояние |1⟩, то функция сбалансированная.
Создатель формулы Исаенко Вадим Валерьевич.