Биоинформатика подхода к прогнозированию рака с использованием квантового кластерного алгоритма для поведенческого сходства экспрессии генов

Краткое содержание

Этот протокол направлен на кластеризацию данных экспрессии генов для классификации рака с помощью гибридного квантового алгоритма K-Means, который автоматически обнаруживает оптимальное количество кластеров и эффективно их разделяет, продвигая биоинформатику на устройствах Noisy Intermediate-Scale Quantum (NISQ).

Аннотация

В данном исследовании введён гибридный квантовый алгоритм кластеризации K-Means с автоматическим обнаружением кластеров для классификации данных экспрессии раковых и нераковых генов. Метод использует квантовое многофункциональное отображение для кодирования состояний, квантовую оценку расстояния на основе Swap-теста и квантовую градиентную оптимизацию для динамического определения оптимального количества кластеров путём минимизации внутрикластерной дисперсии. Начальные центроиды выбираются с помощью стратегии пропорционального расстояния вероятности, что повышает стабильность и точность. Применяемый к наборам данных по раку молочной железы, этот подход превосходит существующий квантовый алгоритм K-Means, достигая Silhouette Score 0,641 (по сравнению с 0,601), индекс Калински-Харабаша 766,57 (по сравнению с 617,65) и индекс Дэвиса-Боулдина 0,659 (по сравнению с 0,704). Эти результаты указывают на превосходную компактность и разделение кластеров. Хотя предлагаемый алгоритм демонстрирует немного более высокую временную сложность O (N_{×K max}×_{M obs}) благодаря итеративной оптимизации, он значительно превосходит заранее определённые квантовые K-средние по точности кластеризации, снижению ошибок и практической осуществимости. Её эффективность в обработке данных с большими размерами и устойчивость к квантовому шуму подчеркивают потенциал реальных применений в биоинформатике, особенно в классификации рака с использованием профилей экспрессии генов.

Введение

В биомедицинской инженерии, биоинформатике, статистике, социальных науках и экономике кластеризация является фундаментальным методом организации данных в осмысленные однородные группы. Например, топологический анализ данных (TDA) применялся к наборам данных экспрессии генов рака для выявления структурных закономерностей в высокомерных^{пространствах. 1}. Кластеризация организует данные так, чтобы объекты с высокой сходностью попадали в один кластер, а разные объекты — разным кластерам. Это относится к обучению без надзора и не требует маркировки обучающих данных.

За последние несколько десятилетий было разработано множество алгоритмов кластеризации. Классические подходы включают кластеризацию на основе^{разбиений 2˒3}, кластеризацию^{на основе плотности 4,5}, иерархическую^{кластеризацию 6,7}, кластеризацию на основе^{сетки 8˒9} и кластеризацию на основе^{моделей 10}. Обзоры этих методов выделяют их сильные стороны, а также их ограничения¹¹. Хотя они эффективны в определённых контекстах, большинство классических алгоритмов испытывают трудности с данными с высокой размерностью, шумом или нерегулярным распределением. Следовательно, универсального метода кластеризации, который бы работал оптимально для всех типов данных, не существует.

Для решения этих проблем квантовая кластеризация стала перспективной альтернативой¹². В отличие от классических алгоритмов, квантовые подходы используют суперпозицию, запутанность и другие принципы квантовой механики для более эффективного изучения пространств данных. Эта парадигма становится всё более признанной в исследовательском^{сообществе 13}˒¹⁴˒¹⁵˒¹⁶˒¹⁷˒¹⁸, поскольку демонстрирует потенциальные преимущества по сравнению с классической кластеризацией при обработке высокомерных и шумных наборов данных. Тем не менее, существующие методы квантовой кластеризации часто страдают от заранее определённого количества кластеров или нестабильной инициализации центроидов, что снижает их устойчивость в практических приложениях.

В этой работе вводится новый алгоритм кластеризации на основе распределения гибридных квантовых K-средних, включающий четыре различных новшества: (i) квантовое многофункциональное отображение для кодирования данных экспрессии генов в высокомерное гильбертово пространство; (ii) инициализация центроидов на основе вероятностно-пропорционального расстояния, повышающая стабильность по сравнению с случайной инициализацией; (iii) Оценка квантового расстояния на основе тестов замены для точного измерения сходства; и (iv) Квантовая градиентная оптимизация для динамического определения оптимального количества кластеров путём минимизации внутрикластерной дисперсии. Эти достижения отличают предлагаемый метод от предыдущих подходов квантовой кластеризации^19,20, повышая устойчивость, масштабируемость и применимость в реальных биоинформатиках.

Кластеризация данных экспрессии генов является критически важной задачей в биоинформатике, особенно для различения раковых и нераковых клеток на основе их генетических профилей. Традиционные методы кластеризации, такие как классический K-Means, часто испытывают трудности с высокомерным характером наборов данных экспрессии генов, что приводит к неоптимальной классификации. Для преодоления этих трудностей мы вводим квантовый алгоритм K-Means с оптимальным определением кластера, который использует квантовое отображение признаков и вероятностную инициализацию центроидов для достижения превосходной производительности кластеризации. Этот алгоритм не только эффективно кластеризует данные экспрессии генов, но и автоматически определяет оптимальное количество кластеров, что позволяет выявлять отдельные подтипы рака

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

Протокол

1. Квантовое отображение признаков

Кодирование классических точек данных в квантовые состояния достигается путём их отображения в квантовое гильбертово пространство, к которому можно эффективно обращаться и управлять квантовым^{компьютером 16}˒^17,19. Этот процесс использует нелинейное квантовое отображение признаков, которое встраивает классические данные в гильбертово пространство (рисунок 1). Фиксированная карта квантовых схем преобразует входные точки данных в^{квантовые состояния 17}, а вариационные схемы позволяют выполнять задачи машинного обучения, адаптируя базу^{измерения 22}. Вариационная схема состоит из набора параметризованных квантовых элементов, оптимизированных с помощью гибридных квантово-классических^{методов 23}.

Рисунок 1: Отображение признаков в квантовом гильбертовом пространстве. Пожалуйста, нажмите здесь, чтобы увидеть увеличенную версию этой фигуры.

2. Кодирование целевой точки и центроидов в кубиты

Для кодирования признаков наших точек данных нужно выполнять вращения с помощью элементов U3.

Это поворачивает радианы θ кубита от положительной оси z, а Φ радианы — от положительной оси x.

Все кубиты инициализировались в состоянии ∣0〉 до начала процесса кодирования. Каждое значение экспрессии гена нормализовалось до диапазона [0,1] и преобразовано в угол вращения с использованием отношения θ_i=πx_i. Затем к каждому кубиту применялся параметризованный унитарный элемент для кодирования соответствующей функции, реализованный в Qiskit с помощью операции qc.u(theta_i, pi, pi, qubit_index). При кодировании нескольких признаков процедура вращения повторялась по соответствующим кубитам для создания многофункционального представления. После этих операций полученное квантовое состояние ∣ψ〉 представляло закодированный вектор признаков в гильбертовом пространстве. На этом этапе измерения не проводились, так как подготовленное состояние было зарезервировано для последующей оценки сходства.

3. Сравнение квантовых состояний

Результаты квантовых экспериментов по своей природе случайны, потому что кубиты по своей природе нестабильны, как описано в квантовой физике. Следовательно, выводы и прогнозы должны выражаться с помощью вероятностей и неопределённостей. Таким образом, сделать однозначные выводы представляет собой настоящий вызов. Однако, когда рассматриваемые квантовые состояния чисты, различия между состояниями (с ненулевой вероятностью) можно однозначно предсказать с помощью^{экспериментов 24}˒²⁵.

Два квантовых состояния, ∣ψ〉 и ∣φ〉, сначала загружались в отдельные квантовые регистры. Затем в состоянии ∣0〉 инициализировался дополнительный кубит для управления операцией замены. К помощнику применялся элемент Адамара для размещения её в суперпозиции перед выполнением управляемой операции SWAP. Элемент Фредкина (CSWAP) использовал асциллу в качестве управляющего кубита и два регистра данных в качестве целей, что позволяло создавать помехи между состояниями. После этой операции на асциллу был установлен второй затвор Хадамарда для завершения интерференционной картины. Измерялся только анцилловый кубит, и его результат закодировал сходство между двумя состояниями. Когда состояния были идентичны, анцилла давала результат 0 с вероятностью 1, тогда как ортогональные состояния давали результат 0 с вероятностью 0.5.

Рисунок 2: Иллюстрация сравнения на основе вероятностей. Если состояния ρ и ξ различаются, то наблюдаемое распределение вероятностей принадлежит _{P E}⁻ \ _{P E}⁺. Пожалуйста, нажмите здесь, чтобы увидеть увеличенную версию этой фигуры.

Оператор плотности ρ связан с любым квантовым состоянием ρ ∈ S(H), таким образом, что tr[ρ] = 1, а ρ ≥ 0. Здесь множество всех состояний S(H) системы, которое будет ассоциироваться с гильбертовым пространством H. Положительная измеряющая показатель оператора (POVM) — это квантовая статистическая измерение признаков, представляющее собой набор положительных операторов E₁, . . . , E_n как E (действующих на H) и тождественности I = . Распределение вероятностей присваивает измерение E для каждого состояния ρ ∈ S(H), где p_j = tr[_{E j}ρ]≥ 0 и =^{1 26}.

4. Сравнение квантовых состояний на основе SWAP

Разницу между двумя квантовыми состояниями можно измерить с помощью процедуры тестирования SWAP в квантовых вычислениях. Этот метод был впервые представлен Баренко и соавторами.²⁷ и позже заново открыты Джоном Уотрусом, Рональдом де Вольфом, Гарри Бурманом и ^{Ричардом Кливом 28}. Тест SWAP применялся к квантовым вычислениям и квантовому машинному ^{обучению 15, 29}.

Тест SWAP принимает входные состояния ∣ψ〉 и ∣φ〉 и выводит 1 (случайную величину Бернулли) с вероятностью 1/2 - 1/2〈φ,ψ〉² , что оценивает квадрат произведения двух ^{состояний 30}.

Объяснение схемы

Рассмотрим два состояния ∣φ〉 и ∣ψ〉 системы, протокол в начале равен ∣0,φ,ψ〉. После применения ворот Адамара состояние меняется на ∣0,φ,ψ〉 + ∣1,φ,ψ〉. Элемент CSWAP преобразует состояние в (0,φ,ψ〉 + ∣1,ψ,φ〉). После второго ворота Адамара состояние становится 1/2(|0,φ,ψ〉 + ∣1,φ,ψ〉 + |0,ψ,φ〉 - ∣1,ψ,φ〉)= 1/2∣0〉(|φ,ψ〉 + |ψ,φ〉) +  1/2|1〉(|φ,ψ〉 - |ψ,φ〉). Затем измеряется первый кубит, вероятность получения результата 0 равна P(Первый кубит = 0) = 1/2 (〈φ|〈ψ| + 〈ψ|〈φ|) 1/2 (|φ,ψ〉 + |ψ,φ〉) = 1/2 + 1/2 |〈ψ|φ〉|². Если ψ и φ ортогональны (|〈ψ|ϕ〉|² = 0), тогда вероятность получения 0 равна 1/2. Если состояния идентичны (|〈ψ|ϕ〉|² = 1) тогда вероятность получения 0 равна 1. ²⁴

Рисунок 3: (a) Схема затвора Фредкина с противоположным состоянием, (b) Выход графа измеряемого вероятностями, (c) Схема затвора Фредкина с затвором Адамара, (d) Выход графа измеряемых вероятностями. Пожалуйста, нажмите здесь, чтобы увидеть увеличенную версию этой фигуры.

Схема использовала один помощник кубита вместе с двумя регистрами, кодировавшими квантовые состояния ∣ψ〉 и ∣φ〉. Все кубиты инициализировались до начала этапа кодирования. Признаки экспрессии генов затем кодировались в соответствующих регистрах с помощью процедуры отображения признаков. Элемент Адамара применялся к анцилловому кубиту для создания суперпозиции, после чего выполнялась операция управляемой SWAP между двумя регистрами состояний с асциллой в качестве управления. Второй гейт Хадамарда был приложен к анцилле для завершения интерференционной картины, а затем измерили кубит помощника. Когда два закодированных состояния были идентичны, анцилла стабильно давала результат 0. Когда состояния были ортогональными, анцилла давала результат с вероятностью 0,5. Для частично похожих состояний вероятность получения 0 была от 0,5 до 1, что отражает степень сходства между состояниями.

5. Оценка квантового расстояния

В классическом анализе данных расстояния между точками данных можно вычислять напрямую с помощью таких показателей, как евклидово или манхэттенское ^{расстояние 2,3}. В случае кубитов на квантовом компьютере эта задача сложнее из-за вероятностной природы квантовых состояний. Хотя фазовые различия и амплитуды вероятности можно измерить, их нельзя напрямую представить как расстояния между двумя ^{векторами 24, 26}.

Для кластеризации необходимо оценить относительные положения точек данных относительно центроидов^{кластера 13}. Чтобы назначить каждый кубит соответствующему кластеру, необходимо определить параметр, который служит индикатором близости к соответствующему центроиду кластера.

Для этого вводится параметр, положительно коррелирующий с сходством, функционирующий как альтернатива традиционным измерениям ^{расстояния 15,30}.

Процесс оценки расстояния начинался с нормированного квантового состояния ∣Ψ〉 и нулевого инициализованного вспомогательного кубита ∣_{q 0}〉. Целью было оценить расстояние между новой точкой данных, закодированной в ∣_{q 1}〉, и центроидом кластера, закодированным в ∣_{q 2}〉. Для подготовки суперпозиции, необходимой для интерференционного рисунка, к асцилловому кубиту применялся элемент Адамара, который создавал состояние ( ∣0〉 + ∣1〉 ) ⊗ ∣Ψ〉 ). Затем применялся управляемый SWAP (Фредкин) элемент с анциллой в качестве контроля, который запутывал анциллу с двумя закодированными состояниями и позволял их перекрытию влиять на результат измерения. Эта операция создавала состояние ( ∣0〉 ⊗ ∣Ψ〉 + ∣1〉 ⊗ F_swap(∣Ψ〉)), из которого можно было извлечь расстояние, основанное на основе произведения, последующим измерением анциллы.

Реализация и вывод схемы

Эта квантовая схема кодирует данные экспрессии генов в кубиты с помощью фазового кодирования, а затем сравнивает два состояния экспрессии генов через элемент Controlled-Swap (CSwap), также известный как Swap^{Test 12}.

Для создания необходимой суперпозиции к всем кубитам (q₀ –q₄) применяются элементы Адамара, что приводит к равной суперпозиции всех базовых состояний |Ψ〉 = , Эта инициализация позволяет параллельно вычислять по нескольким значениям экспрессии генов. Каждый кубит затем проходит фазовое вращение, , где θ_x соответствует отображаемому значению экспрессии гена. Унитарные операторы U(θ,π,π), применяемые к кубитам_{q 1-q 4} , кодируют уровни экспрессии отдельных генов, при этом каждый угол θ представляет трансформированную версию экспрессии гена. Эта процедура отображает классические биологические данные в квантовые состояния посредством фазового кодирования, позволяя представлять несколько генов в квантовом пространстве с высоким^{размером 6}.

Затем элементы CSwap используются для сравнения закодированных состояний путём их запутывания. Вспомогательный кубит q₀ выступает в роли контроля, определяя, поменяются ли местами состояния q_{1-q 4} . Аналогичные квантовые состояния порождают конструктивную интерференцию в_{q 0}, что увеличивает вероятность измерения ∣0〉. Наоборот, разные состояния увеличивают вероятность измерения ∣1〉. Последующий затвор Адамара на_{q 0} обеспечивает амплитудную интерференцию, позволяя извлекать информацию о сходстве посредством измерений.

Пусть два квантовых состояния ∣ψ〉 и ∣φ〉 представляют собой разные наборы данных экспрессии генов, |ψ〉 = ∑_ia_i |i〉, |φ〉 = ∑_ib_i |Я... .

Тест обмена оценивает точность (внутреннее произведение) между ними:

P (0) = ,

где ∣〈ψ∣φ〉∣ обозначает внутреннее произведение. Если P(0) ≈ 1, состояния схожи; если P(0) ≈ 0,5 или ниже, они различаются.

Эта структура позволяет сравнивать наборы данных между пациентами или экспериментальными состояниями (например, нормальная и заболевшая ткань). Он обеспечивает эффективную основу для кластеризации высокомерных данных в квантовых моделях машинного обучения. Swap Test поддерживает выявление сходств между квантовыми состояниями, что может использоваться для группировки образцов в значимые^{кластеры 4}.

Рисунок 4: Схема измерения расстояния между точками данных и центроидами. Пожалуйста, нажмите здесь, чтобы увидеть увеличенную версию этой фигуры.

Рисунок 5: Вывод графика измеряемых вероятностями. Пожалуйста, нажмите здесь, чтобы увидеть увеличенную версию этой фигуры.

Точка данных сначала кодировалась в квантовом состоянии ∣ψ〉, а соответствующий кластерный центроид кодировался в состоянии ∣φ〉. Затем была выполнена процедура тестирования замены, описанная ранее, для сравнения этих двух состояний, и была зафиксирована вероятность вспомогательного измерения P(0). Верность между состояниями получалась как F=∣〈ψ∣φ〉∣², а квантовое расстояние определялось как D (ψ,φ) = . Меньшее значение D указывало на то, что точка данных ближе к центроиду в квантовом пространстве признаков.

6. Начальный выбор центроидов

Инициализация кластерных центроидов критически важна для стабильности и точности кластеризации K-Means. Рандомизированный отбор может привести к плохо распределенным центроидам, что приводит к медленной сходимости и неоптимальным результатам. Для решения этой проблемы используется метод вероятностно-пропорционального расстояния, вдохновлённый стратегией K-Means^{++ 20} . В квантово-усиленном подходе расстояния оцениваются с помощью Quantum Distance Estimator на основе теста SWAP, что гарантирует, что выбранные центроиды лучше отражают базовое распределение данных. Эта стратегия улучшает разделение кластеров и повышает устойчивость алгоритмов, особенно в наборах данных с высокой размерностью.

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

7. Расчёт квантовой дисперсии

Дисперсия кластера количественно определяет компактность точек данных вокруг их центроидов, что делает её ключевым показателем для оценки качества кластеризации. В классических K-средних дисперсия вычисляется как среднее квадрат расстояния между точками данных и назначенными им центроидами. В квантово-усиленном подходе эти расстояния получаются с помощью Quantum Distance Estimator (с помощью теста SWAP), который вычисляет сходства между квантовыми состояниями, основанные на достоверности. Суммируя квадраты расстояний внутри каждого кластера и нормализуя по размеру кластера, получаем значение дисперсии, отражающее степень внутрикластерной когезии. Минимизация этой дисперсии обеспечивает более плотные и значимые кластеры, что особенно важно в высокоразмерных наборах данных по экспрессии генов для различения раковых и нераковых образцов.

Распределение кластеров выполнялось путём назначения каждой закодированной квантовой точки данных ближайшему центроиду с помощью оценки квантового расстояния. Для каждого кластера C_k вычислялось квантовое расстояние D(_{ψ i,C k}) между каждой точкой данных и её центроидом. Дисперсия внутри кластера затем вычислялась с помощью , которое измеряло компактность каждого кластера. Общая дисперсия была получена путём суммирования отдельных дисперсий по всем кластерам. Это общее значение дисперсии фиксировалось для определения оптимального количества кластеров и оценки общей эффективности кластеризации.

8. Квантовая градиентная оптимизация

Определение оптимального количества кластеров (K) является фундаментальной задачей в задачах кластеризации. Традиционные K-средние требуют предопределения K , что часто приводит к недо- или чрезмерной кластеризации. В нашем квантово-усиленном подходе мы интегрируем квантовую градиентную оптимизацию (QGBO ) для адаптивного определения оптимального количества кластеров. Алгоритм итеративно увеличивает K, пересчитывает дисперсию на каждом шаге и оценивает уменьшение дисперсии (ΔV). Когда улучшения дисперсии опускаются ниже порога, кластеризация прекращается. Квантовый градиент вычисляется с помощью правила смещения параметров, которое оценивает производные ожидаемых значений из квантовых схем. Такой подход гарантирует, что итоговое количество кластеров балансирует точность и эффективность, что делает его особенно полезным в биоинформатике, где истинное количество биологических подтипов заранее неизвестно.

Процесс кластеризации начался с K=1, а общая дисперсия V(K) вычислялась с помощью процедуры квантового расчёта дисперсии. Количество кластеров было увеличено до K+1, и дисперсия V(K+1) была пересчитана. Снижение дисперсии, ΔV=V(K)−V(K+1), было оценено, чтобы определить, продолжают ли дополнительные кластеры улучшать компактность данных. Итерация прекратилась, когда ΔV упал ниже заранее заданного порога, что указывало на то, что дальнейшее увеличение K не привело к значимым улучшениям. Была построена параметризованная квантовая схема с вариационными элементами для мониторинга изменений кривизны в тенденции дисперсии, и эта информация направляла процесс оптимизации кластера. Оптимальное количество кластеров было выбрано как значение K , при котором редукция дисперсии стабилизировалась, что приводило к компактным и хорошо разделённым кластерам.

9. Расчёт дисперсии кластера и хранение в_списке V

После формирования стабильных кластеров алгоритм вычисляет дисперсию кластера для измерения компактности каждого кластера. Дисперсия V_кДж для данного кластера определяется с помощью расстояний между каждой точкой данных в кластере и центроидом кластера:

где: x — образец экспрессии генов, C_i — кластер, C_ci — центроид кластера C_i, V_kj — дисперсия, зафиксированная для ^j-й итерации с k кластерами.

Эта дисперсия хранится в списке V, который позже будет использоваться для определения оптимального количества кластеров.

10. Определение оптимального количества кластеров

Для поиска оптимального количества кластеров K алгоритм выполняет несколько итераций, соблюдая разные начальные условия. Ключевые шаги включают:

Алгоритм сначала определил минимальное значение дисперсии из списка дисперсий, вычисленных для различных значений K. Снижение дисперсии между последовательными подсчётами кластеров затем измерялось с помощью выражения ΔV=∣V_k−V_k−1∣, где V_k означала дисперсию для K кластеров, а V_k−1 — дисперсию для кластеров K−1 . Если снижение ΔV опускалось ниже заранее заданного порога, что указывало на незначительное улучшение кластеризации, процедура завершалась. В противном случае количество кластеров увеличивалось, и вычисление повторялось до достижения оптимального количества кластеров.

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

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

Один кластер, представляющий раковые клетки (отмеченные характерными сигнатурами экспрессии генов, связанными с злокачественными опухолиями).

Один кластер представляет собой нераковые клетки (с нормальными профилями экспрессии генов).

Параметры, переменные и константы, используемые в предложенном алгоритме кластеризации Quantum K-Means, перечислены в таблице 1. Определите размеры набора данных, установите количество кластеров K и примените критерии остановки и пороги оптимизации для управления процессом. Настройте вычислительные параметры, такие как количество выстрелов за пробег и случайный seed, чтобы обеспечить воспроизводимость. Инициализуйте центроиды с помощью метода отбора на основе вероятностей и обновляйте их итеративно до сходимости. Таблица также указывает ожидаемые результаты, включая метки кластера, центроиды, оптимальный K, метрики оценки и графики визуализации.

Категория	Параметр	Ценность / Стандарт	Примечания
Набор данных	Набор данных по раку молочной железы	569 образцов × 32 признаков (сокращено до 2 компонентов PCA)	Размерность, уменьшенная с помощью PCA
Количество скоплений	K	Динамический, сначала 1, до 5	Оптимизировано с помощью уменьшения дисперсии
Максимальные скопления	Kmax	5	Верхняя граница поиска
Количество ударов за пробежку	N	1024	Измерения на выполнение схемы
Прекращение толерантности	ε	1 × 10^-14	Критерий сходимости дисперсии
Порог наклона дисперсии	ΔV	9.9 × 10^-4	Порог остановки для оптимизации
Наблюдения	Mobsrv	3	Независимые пробеги на размер кластера
Предел итерации	–	10	Максимальные шаги обновления центроидов за один запуск
Случайный сид	–	42	Обеспечивает воспроизводимость
Ожидаемые результаты	–	Метки кластера, центроиды, оптимальный K, метрики оценки, графики	Экспортировано в виде .csv и .png файлов
Дисперсии между кластерами	Vlist	пусто	Обнаруживает оптимальное K
Центроид j	CJ	Инициализация по функции (на основе вероятностей, пропорциональных квадрату расстояний точек)	Обновление итеративно и сохранение конечных центроидов

Таблица 1: Материалы, программное обеспечение и настройки воспроизводимости

Шаг	Функция / API (из вашего кода)	Бой	Ожидаемый результат
Кодирование признаков	qc.u(тета, пи, пи, кубит)	Кодировать нормализованную классическую особенность в вращение кубита	Состояние кубитов
Тест SWAP / квантовое расстояние	get_Distance(x, y) с использованием qc.cswap()	Постройте схему из 3 кубитов (анциллу + два состояния)	Идентичные → P(0) ≈ 1.0; ортогональный → P(0) ≈ 0,5
Исполнение схем	SamplerV2 с AerSimulator (1024 выстрела)	Запускайте схему на симуляторе с транспиляцией (OPT уровень 1)	Вероятностное распределение для анциллового кубита
Инициализация центроидов	initialize_centroids_kmeans_pp(очки, k)	Выберите начальные центроиды, пропорциональные расстоянию	Разнообразные стартовые центроиды
Перераспределение кластеров	find_nearest_neighbour(точки, центроиды)	Назначайте точки ближайшему центроиду	Членство в стабильных кластерах
Расчёт дисперсии	calculate_variance(центры, centers_distance)	Вычисление внутрикластерной дисперсии	Дисперсия уменьшается с каждой итерацией
Уклон дисперсии	grad_slope(k, V_k, k-1, V_k-1)	Сравните ΔV с ε = 1e-14 и порогом наклона ΔV ≤ 0,000099	Обнаружено оптимальное K
Визуализация	matplotlib.pyplot, plot_histogram	Назначение кластеров графика и квантовые результаты	Диаграммы рассеяния PCA, диаграммы дисперсии, гистограммы
Метрические вычисления	silhouette_score, calinski_harabasz_score, davies_bouldin_score	Оценка качества кластеризации	Silhouette ≈ 0.64, CH ≈ 766, DB ≈ 0.65

Таблица 2: Выполнимые детали реализации предлагаемого алгоритма.

Реализация и алгоритмы

Квантовый алгоритм K-Means с оптимальным определением кластера — это квантово-усиленный метод кластеризации, который динамически определяет оптимальное количество кластеров с использованием квантового отображения^{признаков 19} Процедура начинается с рассмотрения всех точек данных как принадлежащих одному кластеру. Количество кластеров K затем постепенно увеличивается. Центры кластеров инициализируются вероятностно в зависимости от межточечных расстояний, после чего каждой точке данных присваивается ближайшему центроиду, образуя K кластеров. Далее рассчитывается дисперсия кластера, и обновляются центроиды. Этот процесс перераспределения повторяется итеративно, пока дальнейших изменений не произойдёт.

Алгоритм оценивает дисперсию по нескольким итерациям, сохраняя значения дисперсии, соответствующие разным количеству кластеров. Оптимальное значение K определяется путем минимизации дисперсии при мониторинге снижения дисперсии ΔV. Если ΔV становится незначительно малым, процедура прекращается; в противном случае K увеличивается, и процесс кластеризации заново запускается. Эта адаптивная стратегия обеспечивает эффективное и точное разбиение данных, особенно в пространствах признаков с высокой размерностью.

Рисунок 6: Блок-схема предлагаемой процедуры кластеризации гибридного квантового квантового K-Means, показывающая квантовое отображение признаков, инициализацию центроидов, итеративное назначение кластеров, квантовую дисперсию вычисления, проверку сходимости на основе дисперсии и квантовый градиентный выбор оптимального количества кластеров.Пожалуйста, нажмите здесь, чтобы увидеть увеличенную версию этой фигуры.

Следующие шаги описывают квантовый алгоритм K-Means для кластеризации данных экспрессии генов рака и не раковых.

Алгоритм: кластеризация данных экспрессии генов рака и нераковых клеток с использованием алгоритма квантового K-среднего

Шаг 1: Квантовое отображение признаков (многопризначеское кодирование).
Шаг 2: Предполагая, что изначально все точки данных принадлежат одному кластеру, то установим значение K=1 (где K: — нет оптимальных кластеров, V: — дисперсия кластера, а ΔV: уменьшение дисперсии).
Шаг 3: Инициализация центров (выбор начальных центральных точек с использованием вероятностной доли расстояний между точками данных).
Шаг 4: Назначьте каждую точку данных ближайшему центроиду, который сформирует заранее определённые кластеры 'K'.
Шаг 5: Вычислите дисперсию кластера и разместите новый центроид каждого кластера.
Шаг 6: Повторите шаг 4, то есть переназначите каждую точку данных новому ближайшему центроиду каждого кластера.
Шаг 7: Если произойдёт какое-либо перераспределение, переходите к шагу 5, иначе переходите на шаг 8.
Шаг 8: Теперь получаем кластер C_j («j'-я итерация с 'k' ни одной из кластеров) и вычисляем дисперсию V_kj= , где 'x': точка данных принадлежит кластеру C_i, а C_ci — центроид кластера C_i. Ведите запись дисперсии V_kj в _списке V и начинайте заново кластеризацию с новыми Центрами с шага 3 (Редко нет раз, то есть 'j' раз, где 1 ≤ j ≤ _{M obsrv}) с той же 'K'.
Шаг 9: Найдите минимальную дисперсию V_{из списка} V с 'K' без кластеров.
Шаг 10: Вычислить ΔV (ΔV = |V_k - V_k-1|, где V_k: — дисперсия с 'K' ни одного из кластеров, а V_k-1: — дисперсия с 'K-1' ни одного из кластеров), если ΔV — это оптимизация на основе квантового градиента (огромная редукция), то FINISH в противном случае увеличите K (K=K+1) и перейдите к шагу 3 с новым 'K'.
Шаг 11: Кластеры готовы, и оптимальный номер кластеров — 'K'.

Алгоритм отображения квантовых признаков

Алгоритм 1: Отображение квантовых признаков

Входы: P указывает на каждое из квантовых состояний |ψ〉 и |Φ〉
Результаты: Оценка | 〈 ψ | Φ〉 |²
Шаги алгоритма:
Шаг 1: Берём кубит и инициализируем его на ноль; применить затвор Адамара и повернуть его от базиса Z к оси X.
Step 2: Устанавливаем φ (0 ≤ φ ≤ π ) в радиане в зависимости от значения точки данных относительно признака 1.
φ = 2*rad(^cos-1)(d₀)), где d₀ представляют значения данных признака 1, а d₀ ∈ [0, 1].
Шаг 3: Мы устанавливаем θ (0 ≤ θ ≤ π ) в радиане в зависимости от значения точки данных относительно признака 2.
θ = 2 * rad(^cos-1(d₁)), где d₁ представляют значения данных признака 2, а d₁ ∈ [0, 1].
Шаг 4: Мы используем квантовый элемент U3 для реализации вращений, выполняющих кодирование признаков точек данных.

Это поворачивает кубит Φ радиана относительно положительной оси x и θ радиана относительно положительной оси z.

Сравнение алгоритма квантовых состояний

Алгоритм 2: Сравнение квантовых состояний

Входные данные: Два кубита |_{q 1}〉 и |q₂〉 — каждое из квантовых состояний |ψ〉 и |Φ〉
Результаты: Оценка | 〈ψ|Φ〉 |²
Шаги алгоритма:
Шаг 1: Рассматривать кубит A как помощник и инициализировать его по состоянию |0〉
Шаг 2: Примените гейт Адамара к кубиту A
Шаг 3: Применить CSWAP к кубитам |_{q 1} 〉 и |q₂ 〉 (в состоянии|ψ〉 и |Φ〉), где A выступает в роли управляющего кубита
Шаг 4: Примените гейт Адамара к кубиту A
Шаг 5: Измерить A на основе Z и записать результат измерения как M
Возвращение M как наша оценка | 〈 ψ|Φ 〉 |²

Алгоритм кластеризации квантового расстояния для k средних

Алгоритм 3: Квантовый оценщик расстояния и выбор нового центроида кластера

Входы: P нет точек данных и K нет центроидов кластеров, каждое из квантовых состояний |ψ〉 и |Φ〉
Результаты: Новый кластерный центроид, связанный с точками данных
Шаги алгоритма:
для i в диапазоне от 1 до P:
Выберите^i-ю точку данных и запишите её на |q_i 〉
для j в диапазоне от 1 до K:
Выберите^j-й кластерный центроид и установите его на |q_j 〉
Сравните квантовые состояния |q_i 〉 и |q_j 〉 то есть^i-й кубит с^j-м центроидом и записываем измерение в M как (_{M i}, j)
конец для
Найдите минимальное расстояние (M_min ,min) от M и множество min — новый центроид |q_i 〉 и записать его как C_i
конец для
Возвращение C как наш новый список центроидов

M= список всех кластерированных центроидных расстояний от |_{q i} 〉 i-го кубита
C = список всех новых вычисленных кластерных центроидов C_i из |q_i 〉; ∀_{(i∈{1,...,P})}

Начальный алгоритм выбора центроидов

Алгоритм 4: Вычислить начальные центроидные точки с использованием вероятностной доли расстояний между точками данных

Входы: m no точек данных (X₁,_{X 2},...,_{X m}), каждое из квантовых состояний |ψ〉 и |Φ〉
Вывод: возврат множества S с K начальными центроидами
Шаги алгоритма:
Шаг 1: Выберите одну точку X случайным образом из точек данных X_i (1 ≤ i ≤ m) и добавьте её в множество S
Шаг 2: Для всех X_i вычислите расстояние между X_i с помощью Квантового оценщика расстояния и ближайшей центроидной точкой в S и установите расстояние как D_dist(X_i)
Шаг 3: Выберите число Y равномерно между 0 и_{D dist}(X₁)² + D_dist (X₂)² + ...+ D_dist (X_m)²
Шаг 4: Найдём уникальное целое число i такое, что
D_dist (X₁)² + D_dist (X₂)² + ...+ D_dist (X_i)² >= Y > D_dist (X₁)² + D_dist (X₂)² + ...+ D_dist (X_i-1)²
Шаг 5: Добавить x_i к S
Шаг 6: Пока не найдётся K центроидов, повторяйте шаги 2–4

Возвращение S как начальные центроидные точки

Алгоритм расчёта квантовой дисперсии

Алгоритм 5: Вычисление квантовой дисперсии

Входные данные: P нет точек данных, каждое из квантовых состояний | ψ〉 и |Φ〉
Вывод: возврат дисперсии точек данных
Шаги алгоритма:
totalДисперсия ← 0
для i в диапазоне от 1 до K:
Выберите^i-й кластерный центроид и установите его на |q_i 〉
totalVariancei ← 0, M ← 0
Для всех J ∈ P, ассоциированный с центроидом кластера i:
Выберите^j-ю точку данных и установите её на |q_j 〉
Сравните квантовые состояния |q_i 〉 и |q_j 〉 то есть^{i-th-центроид} с^j-й точкой данных и записывают измерение в M_j
М ← M + Mj
конец для
_{totalVariance i} ← [C_i —^i-й кластер; |C_i | не является точками данных в i^{кластере}, D_k — точка данных ∈ C_i и_{M k}
— расстояние между центроидом C_i и D_k]
totalДисперсия ← totalVariance + totalVariancei
конец для
возврат totalДисперсия

Алгоритм оптимизации на основе квантового градиента (Оптимальное количество кластеров)

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

Алгоритм 6: Оптимизация на основе квантовых градиентов

Входные данные:
Параметризованная квантовая схема QC(θ) с одним вращательным элементом кубита R_Y(θ).
Квантовая наблюдаемая = Z (ожидаемое значение Паули-Z).
Диапазон значений параметров θ.
Результаты: Вторая производная f′′(θ) ожидаемого значения 〈Z〉 по θ.
Шаги алгоритма:
Шаг 1: Инициализуйте однокубитную квантовую схему QC(θ) с помощью следующего:
Параметризованный элемент вращения R_Y(θ).
Измерение в вычислительном (Z) базисе.
Шаг 2: Определим функцию Evaluate_ Expectation(θ ), то есть f′(θ) =
Привязать параметр θ к схеме.
Выполните схему на квантовом симуляторе с помощью N выстрелов.
Измерять вероятности исхода P(0) и P(1).
Вычислите ожидаемое значение:
f(θ)=P(0)−P(1)
Шаг 3: Вычислите вторую производную с помощью правила сдвига параметров:
Задайте значение сдвига s =
Вычислите значения ожидания в сдвигаемых точках:
f(θ+s), f(θ), f(θ−s)
Вычислим вторую производную:
f ′′(θ) =
Шаг 4: f ′′(θ) для анализа поведения по снижению дисперсии.

Детали реализации предлагаемого подхода квантовой кластеризации приведены в таблице 2. В таблице указаны выполняемые функции и API, используемые на каждом этапе алгоритма, включая кодирование признаков в квантовых схемах, выполнение теста SWAP для оценки расстояния, инициализацию центроидов, итеративное перераспределение кластеров и вычисление дисперсии/ΔV. Также приведены параметры выполнения схемы, такие как использование SamplerV2 с сервером AerSimulator при 1024 выстрелах и транспиляционная оптимизация уровня 1. Кроме того, в таблице представлены методы визуализации, применяемые для создания графиков рассеяния PCA, диаграмм дисперсии и гистограмм, а также метрики оценки кластеризации (silhouette_score, calinski_harabasz_score и davies_bouldin_score). Описывая конкретные функции и API на уровне команд, таблица обеспечивает воспроизводимость всех вычислительных шагов в предлагаемом алгоритме.

Результаты

Хороший кластер будет зависеть от различных факторов, таких как расстояние между кластерами, расстояние между кластерами, критерий дисперсии и т.д. Таким образом, производительность кластеризации оценивалась с использованием трёх стандартных индексов: Silhouette Score, Calinski-Harabasz Index (CH Index) и Davies-Bouldin Index (DB Index). Шкала силуэта измеряет разделение...

Обсуждение

В данном исследовании предлагается новый гибридный квантовый алгоритм кластеризации K-Means с оптимальным обнаружением кластеров, специально разработанный для классификации раковых и нераковых образцов с использованием данных высокомерной экспрессии генов. Подход интегрирует квантовое многофункциональное отображение, квантовую оценку расстояния на основе Swap-теста и квантовую градиентную оптимизацию для динамического определения оптимального количества кластеров. В отли...

Материалы

Список материалов, использованных в этой статье

Имя	Компания	Каталожный номер	Комментарии
Apple MacBook Pro (чип M1)	Apple Inc.	-	8-ядерный процессор / 8-ядерная видеокарта, 16? GB унифицированная память и mdash; используется для локального моделирования
Набор данных экспрессии генов рака молочной железы	Каггл	-	Набор данных с 569 образцами, 32 признаками (уменьшены с помощью PCA в исследовании)
macOS Monterey (операционная система)	Apple Inc.	12.6.9	Среда выполнения на локальной машине
математика (стандартная библиотека Python)	Фонд программного обеспечения Python	встроенный	Основные математические функции
Matplotlib	Сообщество Matplotlib	3.8.4	Построение графиков и визуализация
NoiseModel, QuantumError, ReadoutError (Qiskit Aer)	Проект IBM / Qiskit	часть Aer 0.13.3	Используется для имитации реалистичного квантового шума
NumPy	Разработчики NumPy	1.26.4	Численные операции и обработка массивами
Панды	Команда разработки Pandas	2.2.2	обработка данных, ввод-вывод, табличные операции
Python	Фонд программного обеспечения Python	3.10.12	Язык программирования, используемый в среде Jupyter / IPython
Кискит Аэр	Проект IBM / Qiskit	0.13.3	Бэкенд симулятора с моделированием шума и выполнением
Qiskit IBM Runtime – Session, SamplerV2	Проект IBM / Qiskit	0.41.1	Фреймворк исполнения схем в симуляторе
Кискит Терра	Проект IBM / Qiskit	0.45.0	Квантовая структура для построения и транспилирования схем
scikit-learn	Разработчики SCIKIT-Learn	1.4.2	PCA, метрики кластеризации, предварительная обработка данных