Глава 193: Поиск Гровера в трейдинге

1. Введение

Алгоритм поиска Гровера, предложенный Ловом Гровером в 1996 году, является одним из наиболее значимых результатов в квантовых вычислениях. Он решает фундаментальную вычислительную задачу: имея неструктурированную базу данных из N элементов, найти конкретный элемент, удовлетворяющий определённому условию. Классически для этого требуется O(N) запросов в худшем случае — необходимо проверять каждый элемент по одному. Алгоритм Гровера решает ту же задачу всего за O(sqrt(N)) запросов, обеспечивая доказуемо оптимальное квадратичное ускорение.

В контексте алгоритмического трейдинга это ускорение имеет глубокие последствия. Многие торговые задачи по своей природе комбинаторны: выбор оптимального портфеля из вселенной активов, поиск арбитражных возможностей в большой цепочке опционов или определение лучшего набора параметров для торговой стратегии. Когда пространство поиска растёт экспоненциально — как при рассмотрении всех возможных подмножеств из N активов (2^N возможностей) — даже квадратичное ускорение может сократить вычисления с миллиардов оценок до десятков тысяч.

В этой главе рассматривается применение алгоритма поиска Гровера к торговым задачам. Мы начнём с математических основ усиления амплитуды, рассмотрим конструирование оракула для торговых ограничений и реализуем полный симулятор поиска Гровера на Rust с интеграцией данных криптовалютного рынка Bybit.

Ключевое понимание состоит в том, что алгоритм Гровера не требует какой-либо структуры в данных. В отличие от классических алгоритмов, использующих сортировку, индексацию или другие организационные свойства, алгоритм Гровера рассматривает пространство поиска как чёрный ящик. Это делает его особенно подходящим для торговых задач, где ландшафт пригодности сложен и немонотонен — ситуаций, где классические эвристики могут пропустить оптимальные решения.

2. Математические основы

2.1 Задача поиска

Формализуем задачу поиска следующим образом. Пусть f: {0, 1, …, N-1} -> {0, 1} — булева функция, где f(x) = 1 для ровно M «отмеченных» элементов (решений) и f(x) = 0 для остальных N - M элементов. Наша цель — найти любой x, такой что f(x) = 1.

В квантовой постановке мы кодируем пространство поиска, используя n = ceil(log2(N)) кубитов, где каждое вычислительное базисное состояние |x> представляет один элемент базы данных.

2.2 Равномерная суперпозиция через преобразование Адамара

Алгоритм начинается с подготовки равномерной суперпозиции всех N состояний. Начиная с полностью нулевого состояния |0>^n, мы применяем вентиль Адамара H к каждому кубиту:

|s> = H^{тензор n} |0>^n = (1/sqrt(N)) * sum_{x=0}^{N-1} |x>

Вентиль Адамара для одного кубита действует как:

H|0> = (|0> + |1>) / sqrt(2)
H|1> = (|0> - |1>) / sqrt(2)

Результирующее состояние |s> присваивает равную амплитуду 1/sqrt(N) каждому базисному состоянию, что означает, что каждый элемент имеет равную вероятность 1/N быть измеренным.

2.3 Оператор-оракул

Оракул O_f — это унитарный оператор, который отмечает решения, инвертируя их фазу:

O_f |x> = (-1)^{f(x)} |x>

Для отмеченных состояний (f(x) = 1) амплитуда меняет знак. Для неотмеченных состояний (f(x) = 0) амплитуда остаётся неизменной. Эта инверсия фазы невидима при прямом измерении — вероятности являются квадратами амплитуд, поэтому (-a)^2 = a^2. Магия происходит при комбинации оракула с оператором диффузии.

В торговых приложениях оракул кодирует наши критерии поиска. Например, f(x) = 1 может означать, что конфигурация портфеля x удовлетворяет ограничениям минимальной доходности и максимального риска.

2.4 Оператор диффузии (диффузор Гровера)

Оператор диффузии D выполняет «инверсию относительно среднего». Он определяется как:

D = 2|s><s| - I

где |s> — состояние равномерной суперпозиции, а I — оператор тождества. В вычислительном базисе это действует как:

D_{ij} = 2/N - delta_{ij}

Комбинированная операция G = D * O_f называется итерацией Гровера. Геометрически каждая итерация Гровера вращает вектор состояния в двумерном подпространстве, натянутом на «хорошие» (отмеченные) и «плохие» (неотмеченные) состояния. Угол поворота за итерацию составляет:

theta = 2 * arcsin(sqrt(M/N))

где M — количество отмеченных состояний, а N — общее количество состояний.

2.5 Оптимальное количество итераций

Начиная с равномерной суперпозиции, начальный угол с «плохим» подпространством равен:

theta_0 = arcsin(sqrt(M/N))

После k итераций Гровера угол становится (2k + 1) * theta_0. Мы хотим, чтобы он был как можно ближе к pi/2 (максимизируя вероятность измерения отмеченного состояния). Оптимальное количество итераций:

k_opt = floor(pi / (4 * theta_0)) ≈ (pi/4) * sqrt(N/M)

Для M = 1 это даёт приблизительно (pi/4) * sqrt(N) итераций — знаменитая сложность запросов O(sqrt(N)).

Критически важно, что выполнение слишком большого числа итераций контрпродуктивно. Алгоритм «перелетает» и вероятность успеха уменьшается. Это фундаментально отличается от классического поиска, где больше итераций всегда помогает или, по крайней мере, не вредит.

2.6 Вероятность успеха

После k_opt итераций вероятность измерения отмеченного состояния составляет:

P_success = sin^2((2k_opt + 1) * theta_0) >= 1 - M/N

Для практических целей при правильном количестве итераций вероятность успеха очень близка к 1.

3. Торговое применение

3.1 Выбор подмножества портфеля

Рассмотрим вселенную из n активов. Портфель — это любое подмножество этих активов, что даёт 2^n возможных портфелей. Для n = 20 активов пространство поиска содержит более 1 миллиона конфигураций. Для n = 30 оно превышает 1 миллиард.

Каждый портфель может быть оценён по критериям, таким как:

• Ожидаемая доходность превышает порог r_min
• Дисперсия портфеля (риск) ниже порога sigma_max
• Максимальная просадка в допустимых пределах
• Ограничения диверсификации соблюдены

Алгоритм Гровера может просматривать все 2^n портфелей за O(2^{n/2}) оценок, находя конфигурации, удовлетворяющие всем ограничениям одновременно.

3.2 Обнаружение арбитража в цепочках опционов

Рынки опционов представляют огромные пространства поиска. Один базовый актив может иметь десятки дат экспирации, каждая с десятками страйков, для коллов и путов. Поиск арбитражных возможностей — комбинаций опционов, гарантирующих безрисковую прибыль — требует оценки множества многоножечных комбинаций.

Для k ножек опциона, выбранных из цепочки L листингов, пространство поиска составляет O(L^k). При L = 100 листингах и k = 4 ножках (типичный баттерфлай или кондор спред) пространство поиска составляет 100 миллионов комбинаций. Алгоритм Гровера сокращает это примерно до 10 000 квантовых оценок оракула.

3.3 Оптимизация параметров стратегии

Торговые стратегии часто имеют множество параметров (периоды ретроспективного анализа, пороги, уровни стоп-лосс), которые необходимо совместно оптимизировать. Если каждый параметр имеет d возможных значений и параметров p, пространство поиска равно d^p. Поиск Гровера по этому пространству требует всего d^{p/2} оценок.

4. Конструирование оракула для трейдинга

4.1 Кодирование торговых ограничений

Функция оракула f(x) должна быть закодирована как квантовая схема. Для выбора портфеля каждое n-кубитное состояние |x> представляет подмножество активов (бит j = 1 означает, что актив j включён). Оракул должен вычислить:

f(x) = 1 если expected_return(x) >= r_min И risk(x) <= sigma_max
f(x) = 0 в противном случае

В нашей классической симуляции мы реализуем это непосредственно как вычисление функции. На реальном квантовом компьютере это потребует разложения арифметических операций (взвешенные суммы, сравнения) на элементарные квантовые вентили — нетривиальная, но хорошо изученная задача с использованием квантовых арифметических схем.

4.2 Предварительно вычисленные данные активов

Для оценки метрик портфеля мы предварительно вычисляем статистику по каждому активу из исторических данных:

• Средние доходности для каждого актива
• Ковариационную матрицу для расчёта риска
• Любые дополнительные метрики, релевантные для ограничений

Оракул затем вычисляет доходность портфеля как равновзвешенную сумму доходностей выбранных активов и риск портфеля как соответствующую запись из ковариационной структуры.

4.3 Многокритериальные оракулы

Реальные торговые ограничения включают множество критериев. Мы объединяем их логическим И: портфель отмечается только если ВСЕ критерии выполнены. В модели квантовых схем для этого используются вспомогательные кубиты и мультиконтролируемые вентили. В нашей симуляции мы просто вычисляем составное булево выражение.

5. Пошаговое описание реализации

Наша реализация на Rust состоит из нескольких ключевых компонентов:

5.1 Симулятор вектора состояний

Мы представляем квантовое состояние как комплекснозначный вектор размерности 2^n. Хотя реальные квантовые компьютеры работают с физическими кубитами, классическая симуляция позволяет проверить корректность алгоритма и сравнить с полным перебором.

pub struct GroverSearch {
    num_qubits: usize,
    statevector: Vec<Complex>,
    marked_states: Vec<usize>,
}

Тип Complex хранит действительную и мнимую части как значения f64. Для n кубитов вектор состояний имеет 2^n записей.

5.2 Преобразование Адамара

Мы инициализируем вектор состояний в |0…0> и применяем преобразование Адамара для создания равномерной суперпозиции. Вместо симуляции применения отдельных вентилей мы напрямую устанавливаем каждую амплитуду равной 1/sqrt(N):

pub fn apply_hadamard(&mut self) {
    let n = self.statevector.len();
    let amp = 1.0 / (n as f64).sqrt();
    for state in self.statevector.iter_mut() {
        *state = Complex::new(amp, 0.0);
    }
}

5.3 Применение оракула

Оракул инвертирует амплитуду отмеченных состояний:

pub fn apply_oracle(&mut self) {
    for &idx in &self.marked_states {
        self.statevector[idx].re = -self.statevector[idx].re;
        self.statevector[idx].im = -self.statevector[idx].im;
    }
}

5.4 Оператор диффузии

Оператор диффузии выполняет инверсию относительно средней амплитуды:

pub fn apply_diffusion(&mut self) {
    let n = self.statevector.len();
    let mean = self.statevector.iter()
        .map(|c| c.re)
        .sum::<f64>() / n as f64;
    for state in self.statevector.iter_mut() {
        state.re = 2.0 * mean - state.re;
    }
}

5.5 Выполнение поиска

Полный поиск Гровера объединяет эти шаги:

1. Инициализация равномерной суперпозиции (Адамар)
2. Повторить k_opt итераций: применить оракул, затем применить диффузию
3. Измерение: найти состояние с наибольшей вероятностью

Оптимальное количество итераций вычисляется как:

pub fn optimal_iterations(total_states: usize, num_marked: usize) -> usize {
    let ratio = num_marked as f64 / total_states as f64;
    let theta = ratio.sqrt().asin();
    ((std::f64::consts::PI / (4.0 * theta)) - 0.5).round() as usize
}

5.6 Торговый оракул

Торговый оракул оценивает каждую конфигурацию портфеля по критериям доходности и риска:

pub fn build_trading_oracle(
    returns: &[f64],
    covariance: &[Vec<f64>],
    min_return: f64,
    max_risk: f64,
) -> Vec<usize> {
    // Перебор всех 2^n подмножеств портфелей
    // Отметка тех, что удовлетворяют критериям
}

Для каждого подмножества (представленного как битовая маска) мы вычисляем равновзвешенную доходность и дисперсию портфеля, затем проверяем соответствие заданным порогам.

6. Интеграция с Bybit

Наша реализация получает реальные рыночные данные с биржи Bybit. Мы используем публичный эндпоинт для получения информации о тикерах для нескольких криптовалютных пар.

Конвейер данных работает следующим образом:

1. Получение данных тикеров: Запрос к эндпоинту Bybit /v5/market/tickers для данных спотового рынка
2. Вычисление доходностей: Расчёт процентных изменений цен из 24-часовых данных
3. Оценка ковариации: Построение простой оценки ковариации из доступных метрик
4. Передача в оракул: Использование вычисленной статистики для определения торгового оракула

API Bybit возвращает данные, включающие последнюю торговую цену, 24-часовые максимум/минимум, 24-часовой объём и процент изменения цены за 24 часа. Мы используем процент изменения цены напрямую как нашу оценку доходности.

Для оценки ковариации в производственной системе следует получать исторические данные kline (свечи) и вычислять выборочную ковариационную матрицу. Наш пример использует упрощённую диагональную модель ковариации, основанную на волатильности цен (диапазон максимум-минимум относительно текущей цены).

Код интеграции с API

pub async fn fetch_bybit_tickers(symbols: &[&str]) -> Result<Vec<AssetData>> {
    let client = reqwest::Client::new();
    let resp = client
        .get("https://api.bybit.com/v5/market/tickers")
        .query(&[("category", "spot")])
        .send()
        .await?;
    // Парсинг и фильтрация по запрошенным символам
}

Структура AssetData содержит основные поля, необходимые для нашего оракула:

pub struct AssetData {
    pub symbol: String,
    pub last_price: f64,
    pub price_change_pct: f64,
    pub high_24h: f64,
    pub low_24h: f64,
    pub volume_24h: f64,
}

7. Ключевые выводы

1. Квадратичное ускорение доказуемо оптимально: Алгоритм Гровера достигает сложности поиска O(sqrt(N)), и доказано, что это лучший возможный результат для неструктурированного поиска на квантовом компьютере. Никакой квантовый алгоритм не может добиться лучшего для обобщённого поиска по чёрному ящику.

2. Количество итераций имеет значение: В отличие от классического поиска, где больше усилий всегда помогает, алгоритм Гровера имеет точное оптимальное количество итераций. Слишком мало итераций оставляет вероятность успеха низкой; слишком много итераций заставляют состояние повернуться за оптимальную точку, и вероятность успеха уменьшается.

3. Конструирование оракула — ключевая задача: Теоретическое ускорение реализуется только если оракул может быть эффективно реализован как квантовая схема. Для торговых приложений это требует кодирования финансовых вычислений (доходности, метрики риска, проверки ограничений) в обратимые квантовые вентили.

4. Комбинаторные торговые задачи — естественное применение: Выбор портфеля из N активов имеет 2^N возможных конфигураций. Поиск Гровера сокращает полный перебор с 2^N до 2^{N/2} — для 30 активов с ~1 миллиарда до ~32 000 оценок.

5. Классическая симуляция экспоненциальна: Наша реализация на Rust симулирует алгоритм Гровера классически, что требует O(2^n) памяти и O(2^n * sqrt(2^n)) времени. Реальное преимущество проявляется только на реальном квантовом оборудовании. Тем не менее, симуляция бесценна для верификации и обучения.

6. Гибридные подходы практичны сегодня: Даже без отказоустойчивых квантовых компьютеров понимание алгоритма Гровера информирует разработку квантово-вдохновлённых классических алгоритмов и подготавливает торговые системы к квантовой эре. Вариационные квантовые алгоритмы могут аппроксимировать ускорения типа Гровера на ближнесрочных зашумлённых квантовых устройствах.

7. Интеграция с Bybit демонстрирует практическую применимость: Подключаясь к реальным рыночным данным, мы показываем, что квантовые алгоритмы поиска могут работать с реальными финансовыми данными, а не только с игрушечными примерами. Инфраструктура для приёма данных остаётся классической; квантовое преимущество заключается в самом вычислении поиска.

8. Компромиссы риск-доходность естественно отображаются в ограничения оракула: Фреймворк Марковица с ограничениями доходности и дисперсии напрямую преобразуется в бинарную функцию оракула, делая оптимизацию портфеля учебным применением поиска Гровера.