Abordagem Bioinformática para a Previsão de Câncer usando o Algoritmo de Clustering Quântico para Similaridade Comportamental na Expressão Gênica

Resumo

Esse protocolo visa agrupar dados de expressão gênica para classificação de câncer usando um algoritmo Hybrid Quantum K-Means que detecta automaticamente o número ótimo de clusters e os separa de forma eficiente, avançando aplicações de bioinformática em dispositivos Quânticos de Escala Intermediária Ruidosa (NISQ).

Resumo

Este estudo introduz um Algoritmo Híbrido de Clustering Quântico K-Means com detecção automática de clusters para classificar dados de expressão gênica cancerígena e não cancerosa. O método emprega Mapeamento Quântico Multi-Característica para codificação de estados, estimativa de distância baseada em Teste de Swap e Otimização Baseada em Gradiente Quântico para identificar dinamicamente o número ótimo de clusters, minimizando a variância intra-cluster. Os centróides iniciais são selecionados por meio de uma estratégia de probabilidade e distância proporcional, melhorando a estabilidade e a precisão. Aplicada a conjuntos de dados de câncer de mama, a abordagem supera o algoritmo quântico K-Means existente, alcançando um Score de Silhueta de 0,641 (em comparação com 0,601), um Índice Calinski-Harabasz de 766,57 (comparado a 617,65) e um Índice Davies-Bouldin de 0,659 (comparado a 0,704). Esses resultados indicam uma compacidade e separação superiores dos aglomerados. Embora o algoritmo proposto apresente uma complexidade temporal O ligeiramente maior (N×_{K max}×_{M obs}) devido à otimização iterativa, ele supera significativamente as K-Médias quânticas predefinidas K em precisão de agrupamento, redução de erros e viabilidade prática. Sua eficiência no manuseio de dados de alta dimensão e sua resiliência ao ruído quântico destacam seu potencial para aplicações reais em bioinformática, especialmente na classificação de câncer usando perfis de expressão gênica.

Introdução

Em engenharia biomédica, bioinformática, estatística, ciências sociais e economia, o agrupamento é uma técnica fundamental para organizar dados em grupos homogêneos significativos. Por exemplo, a análise topológica de dados (TDA) foi aplicada a conjuntos de dados de expressão gênica do câncer para revelar padrões estruturais em espaços de alta^{dimensão 1}, o agrupamento organiza os dados de modo que objetos com alta similaridade sejam colocados dentro do mesmo agrupamento, enquanto objetos diferentes sejam atribuídos a agrupamentos diferentes. Isso se enquadra em aprendizagem não supervisionada e não requer dados de treinamento rotulados.

Nas últimas décadas, diversos algoritmos de clustering foram desenvolvidos. Abordagens clássicas incluem agrupamento baseado em^{partição 2}˒³, agrupamento baseado em^{densidade 4,5}, agrupamento hierárquico ^6,7, agrupamento baseado em^{grade 8}˒⁹ e agrupamento baseado em^{modelos 10}. Análises desses métodos destacam seus pontos fortes, mas também suas^{limitações 11}. Embora eficazes em contextos específicos, a maioria dos algoritmos clássicos tem dificuldades com dados de alta dimensão, ruidosos ou distribuídos de forma irregular. Consequentemente, não existe um método universal de agrupamento que funcione de forma ideal em todos os tipos de dados.

Para enfrentar esses desafios, o agrupamento quântico surgiu como uma alternativa promissora¹². Ao contrário dos algoritmos clássicos, abordagens inspiradas em quântico aproveitam a superposição, o emaranhamento e outros princípios da mecânica quântica para explorar espaços de dados de forma mais eficiente. Esse paradigma tornou-se cada vez mais aceito dentro da comunidade de pesquisa¹³˒¹⁴˒¹⁵˒¹⁶˒¹⁷˒¹⁸, pois demonstra vantagens potenciais sobre o agrupamento clássico no manejo de conjuntos de dados de alta dimensão e ruidosos. No entanto, os métodos existentes de clustering quântico frequentemente sofrem com contagens de clusters predefinidas ou inicialização instável do centroide, que reduzem sua robustez em aplicações práticas.

Neste trabalho, é apresentado um novo algoritmo híbrido de Clustering Quântico K-Means baseado em partições, incorporando quatro inovações distintas: (i) Mapeamento Quântico Multi-Característica para codificar dados de expressão gênica em espaço de Hilbert de alta dimensão; (ii) inicialização baseada em centroide proporcional à probabilidade de distância, melhorando a estabilidade em comparação com a inicialização aleatória; (iii) Estimação de distância quântica baseada em Swap Test para medição precisa de similaridade; e (iv) Otimização Baseada em Gradiente Quântico para determinar dinamicamente o número ótimo de clusters minimizando a variância intra-cluster. Essas contribuições distinguem o método proposto das abordagens anteriores de clustering^{quântico 19,20}, aumentando robustez, escalabilidade e aplicabilidade em cenários reais de bioinformática.

Agrupar dados de expressão gênica é uma tarefa crítica em bioinformática, especialmente para distinguir entre células cancerosas e não cancerosas com base em seus perfis genéticos. Métodos tradicionais de agrupamento, como os K-Means clássicos, frequentemente têm dificuldades com a natureza de alta dimensão dos conjuntos de dados de expressão gênica, levando a uma classificação subótima. Para superar esses desafios, introduzimos o Algoritmo Quântico K-Means com Determinação Ótima de Clusters, que utiliza Mapeamento Quântico de Características e inicialização probabilística de centroides para alcançar desempenho superior em clustering. Esse algoritmo não só agrupa os dados de expressão gênica de forma eficiente, mas também determina automaticamente o número ótimo de clusters, permitindo a identificação de subtipos distintos de câncer

O algoritmo proposto é aplicado a conjuntos de dados que contêm perfis de expressão gênica tanto cancerígena quanto não cancerosa, agrupando-os com base na similaridade comportamental para avaliar sua eficácia.

Protocolo

1. Mapeamento de Características Quânticas

A codificação de pontos de dados clássicos em estados quânticos é feita mapeando-os em um espaço de Hilbert quântico, que pode ser acessado e manipulado eficientemente por um computador quântico¹⁶˒^17,19. Esse processo emprega um mapa quântico de características não linear que incorpora dados clássicos no espaço de Hilbert (Figura 1). Um mapa de características fixo de circuitos quânticos transforma os pontos de dados de entrada em^{estados quânticos 17}, enquanto circuitos variacionais possibilitam tarefas de aprendizado de máquina adaptando a base^{de medição 22}. Um circuito variacional consiste em um conjunto de portas quânticas parametrizadas, otimizadas por técnicas híbridas quântica-clássica²³.

Figura 1: Mapeamento de características no Espaço Quântico de Hilbert. Por favor, clique aqui para ver uma versão ampliada desta figura.

2. Codificação do Ponto Alvo e dos Centroides em qubits

Para codificar as características dos nossos pontos de dados, precisamos realizar rotações usando portas U3.

Isso rotaciona o qubit θ radianos para longe do eixo z positivo, e Φ radianos do eixo x positivo.

Todos os qubits eram inicializados no estado ∣0〉 antes do início do processo de codificação. Cada valor de expressão gênica foi normalizado para a faixa [0,1] e convertido em um ângulo de rotação usando a relação θ_i=πx_i. Uma porta unitária parametrizada era então aplicada a cada qubit para codificar a característica correspondente, implementada no Qiskit usando a operação qc.u(theta_i, pi, pi, qubit_index). Quando múltiplas características eram codificadas, o procedimento de rotação era repetido entre os qubits apropriados para criar uma representação multi-características. Após essas operações, o estado quântico resultante ∣ψ〉 representava o vetor de características codificado no espaço de Hilbert. Nenhuma medição foi realizada durante essa etapa, pois o estado preparado foi reservado para estimativas subsequentes de similaridade.

3. Comparando Estados Quânticos

Os resultados dos experimentos quânticos são inerentemente aleatórios porque os qubits são instáveis por natureza, como descrito na física quântica. Consequentemente, conclusões e previsões devem ser expressas em termos de probabilidades e incertezas. Tirar conclusões inequívocas, portanto, apresenta um desafio genuíno. No entanto, quando os estados quânticos considerados são puros, diferenças entre estados (com probabilidade não nula) podem ser previstas de forma inequívoca por meio de^{experimentação 24}˒²⁵.

Dois estados quânticos, ∣ψ〉 e ∣φ〉, foram inicialmente carregados em registradores quânticos separados. Um qubit ancilla era então inicializado no estado ∣0〉 para controlar a operação de swap. Uma porta Hadamard foi aplicada ao ancilla para colocá-lo em superposição antes da execução da operação de SWAP controlada. A porta de Fredkin (CSWAP) usava o ancilla como qubit de controle e os dois registradores de dados como alvos, permitindo interferência entre os estados. Após essa operação, uma segunda porta de Hadamard foi aplicada ao ancilla para completar o padrão de interferência. Apenas o qubit ancilla foi medido, e seu resultado de medição codificava a semelhança entre os dois estados. Quando os estados eram idênticos, a ancilla produzia o resultado 0 com probabilidade 1, enquanto estados ortogonais produziam o resultado 0 com probabilidade 0,5.

Figura 2: Ilustração da comparação baseada em probabilidade, se os estados ρ e ξ forem diferentes, então a distribuição de probabilidade observada pertence a P_E⁻ \ P_E⁺. Por favor, clique aqui para ver uma versão ampliada desta figura.

O operador densidade ρ está associado a qualquer estado quântico ρ ∈ S(H), tal que tr[ρ] = 1 e ρ ≥ 0. Aqui, conjunto de todos os estados S(H) de um sistema que estará associado ao espaço de Hilbert H. Medida Valorada por Operador Positivo (POVM) é uma medição de características estatísticas quânticas que é uma coleção de operadores positivos E₁, . . . ,_{E n} como E (que atuam sobre H) e a identidade I = . Uma distribuição de probabilidade atribui a medida E para cada estado ρ ∈ S(H), onde p_j = tr[_{E j}ρ]≥ 0 e =^{1 26}.

4. Comparação de Estados Quânticos Baseada em SWAP

A diferença entre dois estados quânticos pode ser medida usando o procedimento de teste SWAP na computação quântica. Esse método foi introduzido pela primeira vez por Barenco et al.²⁷ anos e posteriormente redescoberta por John Watrous, Ronald de Wolf, Harry Buhrman e Richard ^{Cleve 28}. O teste SWAP foi aplicado à computação quântica e ao aprendizado de máquina ^{quântico 15, 29}.

O teste SWAP toma ∣ψ〉 e ∣φ〉 como estados de entrada e produz 1 (uma variável aleatória de Bernoulli) com probabilidade 1/2 - 1/2〈φ,ψ〉² , que estima o produto interno quadrático dos dois estados ³⁰.

Explicação do circuito

Considere dois estados ∣φ〉 e ∣ψ〉 do sistema, o protocolo no início é ∣0,φ,ψ〉. Após a aplicação do portão Hadamard, o estado é alterado para ∣0,φ,ψ〉 + ∣1,φ,ψ〉. A porta CSWAP transforma o estado em (0,φ,ψ〉 + ∣1,ψ,φ〉). Após o segundo portão Hadamard, o estado passa a ser 1/2(|0,φ,ψ〉 + ∣1,φ,ψ〉 + |0,ψ,φ〉 - ∣1,ψ,φ〉)= 1/2∣0〉(|φ,ψ〉 + |ψ,φ〉) +  1/2|1〉(|φ,ψ〉 - |ψ,φ〉). O primeiro qubit é então medido, a probabilidade de obter o resultado 0 é P(Primeiro qubit = 0) = 1/2 (〈φ|〈ψ| + 〈ψ|〈φ|) 1/2 (|φ,ψ〉 + |ψ,φ〉) = 1/2 + 1/2 |〈ψ|φ〉|². Se ψ e φ são ortogonais (|〈ψ|ϕ〉|² = 0), então a probabilidade de obter 0 é 1/2. Se os estados forem idênticos (|〈ψ|ϕ〉|² = 1) então a probabilidade de obter 0 é 1. ²⁴

Figura 3: (a) Circuito da porta de Fredkin com estado polar oposto, (b) Saída do gráfico medido por probabilidade, (c) Circuito da porta de Fredkin com porta de Hadamard, (d) Saída do gráfico medido por probabilidade. Por favor, clique aqui para ver uma versão ampliada desta figura.

O circuito usava um qubit ancilla junto com dois registradores que codificavam os estados quânticos ∣ψ〉 e ∣φ〉. Todos os qubits foram inicializados antes do início da etapa de codificação. As características de expressão gênica foram então codificadas nos respectivos registradores usando o procedimento de mapeamento de características. Uma porta de Hadamard era aplicada ao qubit ancilla para criar uma superposição, após a qual uma operação de troca controlada era realizada entre os dois registradores de estado, com a ancilla como controle. Uma segunda porta de Hadamard foi aplicada ao ancilla para completar o padrão de interferência, e o qubit ancilla foi posteriormente medido. Quando os dois estados codificados eram idênticos, a ancilga produzia consistentemente o resultado 0. Quando os estados eram ortogonais, a ancilla apresentava o resultado com probabilidade 0,5. Para estados parcialmente semelhantes, a probabilidade de obter 0 estava entre 0,5 e 1, refletindo o grau de similaridade entre os estados.

5. Estimativa de Distância Quântica

Na análise clássica de dados, distâncias entre pontos de dados podem ser calculadas diretamente usando medidas como distância euclidiana ou ^{de Manhattan 2,3}. No caso dos qubits em um computador quântico, essa tarefa é mais complexa devido à natureza probabilística dos estados quânticos. Embora diferenças de fase e amplitudes de probabilidade possam ser medidas, elas não podem ser representadas diretamente como distâncias entre dois vetores ^{24, 26}.

Para agrupamento, é necessário avaliar as posições relativas dos pontos de dados em relação aos centróides^{do cluster 13}. Para atribuir cada qubit ao cluster apropriado, deve ser definido um parâmetro que sirva como indicador de proximidade ao centro correspondente do cluster.

Para alcançar isso, é introduzido um parâmetro que se correlaciona positivamente com a similaridade, funcionando assim como uma alternativa às medidas convencionais de distância ^15,30.

O processo de estimativa de distância começou com um estado quântico normalizado ∣Ψ〉 e um qubit auxiliar inicializado a zero ∣q₀〉. O objetivo era estimar a distância entre o novo ponto de dados codificado em ∣_{q 1}〉 e um centróide de cluster codificado em ∣q₂〉. Para preparar a superposição necessária para o padrão de interferência, uma porta de Hadamard foi aplicada ao qubit ancilla, produzindo o estado ( ∣0〉 + ∣1〉 ) ⊗ ∣Ψ〉 ). Uma porta controlada-SWAP (Fredkin) era então aplicada com o ancilla como controle, que entrelaçava o ancilla com os dois estados codificados e permitia que sua sobreposição influenciasse o resultado da medição. Essa operação produzia o estado ( ∣0〉 ⊗ ∣Ψ〉 + ∣1〉 ⊗_troca F (∣Ψ〉) ), do qual a distância baseada no produto interno podia ser extraída por meio da medição subsequente da ancilla.

Implementação e Saída do Circuito

Esse circuito quântico codifica dados de expressão gênica em qubits usando codificação de fase e, posteriormente, compara dois estados de expressão gênica por meio da porta Controlled-Swap (CSwap), também conhecida como Teste de Swap¹².

Para criar a superposição necessária, portas de Hadamard são aplicadas a todos os qubits (q₀ a_{q 4}), resultando em uma superposição igual de todos os estados da base |Ψ〉 = , Esta inicialização permite o cálculo paralelo sobre múltiplos valores de expressão gênica. Cada qubit então passa por uma rotação de fase, , onde θ_x corresponde ao valor de expressão gênica mapeada. Os operadores unitários U(θ,π,π) aplicados aos qubits q_{1-q 4} codificam os níveis de expressão de genes individuais, com cada ângulo θ representando uma versão transformada da expressão de um gene. Esse procedimento mapeia dados biológicos clássicos em estados quânticos por meio da codificação de fase, permitindo que múltiplos genes sejam representados em um espaço quântico^{de alta dimensão 6}.

As portas CSwap são então usadas para comparar estados codificados por meio de emaranhamento. O qubit auxiliar q₀ atua como controle, determinando se os estados de q_{1-q 4} são trocados. Estados quânticos semelhantes geram interferência construtiva em q₀, resultando em uma maior probabilidade de medir ∣0〉. Por outro lado, estados diferentes aumentam a probabilidade de medir ∣1〉. Uma porta de Hadamard subsequente em q₀ garante interferência de amplitude, permitindo a extração de informações de similaridade por meio da medição.

Suponha que dois estados quânticos ∣ψ〉 e ∣φ〉 representem conjuntos de dados distintos de expressão gênica, |ψ〉 = ∑i a_i |i〉, |φ〉 = ∑_ib_i |i〉 .

O Teste de Swap avalia a fidelidade (produto interno) entre eles:

P (0) = ,

Onde ∣〈ψ∣φ〉∣ denota o produto interno. Se P(0) ≈ 1, os estados são semelhantes; se P(0) ≈ 0,5 ou menos, são diferentes.

Essa estrutura permite a comparação de conjuntos de dados entre pacientes ou condições experimentais (por exemplo, tecido normal vs. doente). Ele fornece uma base eficiente para clustering de dados de alta dimensão dentro de modelos de aprendizado de máquina quântico. O Teste de Swap suporta a identificação de semelhanças entre estados quânticos, o que pode ser utilizado para agrupar amostras em clusters^{significativos 4}.

Figura 4: Circuito de medição da distância entre pontos de dados e centróides. Por favor, clique aqui para ver uma versão ampliada desta figura.

Figura 5: Resultado do gráfico medido por probabilidade. Por favor, clique aqui para ver uma versão ampliada desta figura.

Um ponto de dados era primeiro codificado no estado quântico ∣ψ〉 e o centroide correspondente do cluster era codificado no estado ∣φ〉. O procedimento de teste de swap descrito anteriormente foi então executado para comparar esses dois estados, e a probabilidade de medição ancilla P(0) foi registrada. A fidelidade entre os estados foi obtida como F=∣〈ψ∣φ〉∣², e a distância quântica foi definida como D (ψ,φ) = . Um valor menor de D indicava que o ponto de dados estava mais próximo do centróide no espaço de características quânticas.

6. Seleção Inicial do Centroide

A inicialização dos centróides de cluster é fundamental para a estabilidade e precisão do agrupamento K-Means. A seleção randomizada pode produzir centróides mal distribuídos, levando a convergência lenta e resultados subótimos. Para resolver essa questão, é empregado um método de distância proporcional de probabilidade inspirado na estratégia^{K-Means++ 20} . Na abordagem quântica aprimorada, as distâncias são avaliadas usando o Estimador de Distância Quântica com base no teste SWAP, garantindo que os centroides selecionados representem melhor a distribuição subjacente dos dados. Essa estratégia aprimora a separação de clusters e melhora a robustez algorítmica, especialmente em conjuntos de dados de alta dimensão.

O processo de inicialização do centroide começava selecionando aleatoriamente um ponto de dados para servir como o primeiro centroide. A distância quântica entre esse centróide e cada ponto de dados restante foi então calculada usando o procedimento de estimativa de distância quântica. Com base nesses valores de distância, foi criada uma distribuição de probabilidade na qual cada ponto recebeu uma probabilidade de seleção proporcional à sua distância ao quadrado do centroide mais próximo. Novos centróides foram amostrados de acordo com essa distribuição, e o procedimento foi repetido até que o número desejado de centróides K fosse obtido. Essa abordagem produziu um conjunto inicial de centroides com separação substancialmente melhor do que a seleção aleatória.

7. Cálculo de Variância Quântica

A variância de cluster quantifica a compacidade dos pontos de dados ao redor de seus centróides, tornando-se uma métrica crucial para avaliar a qualidade do agrupamento. Na K-Means clássica, a variância é calculada como a distância média ao quadrado entre pontos de dados e seus centróides atribuídos. Na abordagem aprimorada por quântica, essas distâncias são obtidas usando o Estimador de Distância Quântica (via teste SWAP), que calcula semelhanças baseadas em fidelidade entre estados quânticos. Ao somar distâncias quadráticas dentro de cada cluster e normalizar pelo tamanho do cluster, obtemos um valor de variância que reflete o grau de coesão intra-cluster. Minimizar essa variância garante agrupamentos mais compactos e significativos, o que é particularmente importante em conjuntos de dados de expressão gênica de alta dimensão para distinguir amostras cancerosas e não cancerosas.

A atribuição de cluster era realizada atribuindo cada ponto de dado quântico codificado ao centróide mais próximo usando estimativa de distância quântica. Para cada cluster C_k, a distância quântica D(ψ_{i,C k}) entre cada ponto de dados e seu centróide era calculada. A variância dentro do cluster foi então calculada usando , que mediu a compacidade de cada cluster. A variância total foi obtida somando as variâncias individuais em todos os agrupamentos. Esse valor total de variância foi registrado para determinar o número ótimo de clusters e para avaliar o desempenho geral do agrupamento.

8. Otimização baseada em gradiente quântico

Determinar o número ótimo de clusters (K) é um desafio fundamental na agrupação de tarefas. As K-Means tradicionais exigem que K seja pré-definido, frequentemente levando a subagrupamento ou superagrupamento. Em nossa abordagem quântica aprimorada, integramos a Otimização Baseada em Gradiente Quântico (QGBO) para identificar adaptativamente a contagem ótima de clusters. O algoritmo aumenta iterativamente K, recalcula a variância a cada passo e avalia a redução da variância (ΔV). Quando melhorias na variância caem abaixo de um limite, o agrupamento é encerrado. O gradiente quântico é calculado usando a regra do deslocamento de parâmetro, que estima derivadas dos valores esperados de circuitos quânticos. Essa abordagem garante que o número final de clusters equilibre precisão e eficiência, tornando-a particularmente útil em aplicações de bioinformática onde o número real de subtipos biológicos não é conhecido antecipadamente.

O processo de agrupamento começou com K=1, e a variância total V(K) foi calculada usando o procedimento de cálculo da variância quântica. O número de aglomerados foi então aumentado para K+1, e a variância V(K+1) foi recalculada. A redução da variância, ΔV=V(K)−V(K+1), foi avaliada para determinar se agrupamentos adicionais continuaram a melhorar a compacidade dos dados. A iteração foi interrompida quando ΔV ficou abaixo do limite pré-definido, indicando que aumentos adicionais em K não trouxeram melhorias significativas. Um circuito quântico parametrizado com portas variacionais foi construído para monitorar mudanças de curvatura na tendência de variância, e essas informações guiaram o processo de otimização do cluster. O número ótimo de agrupamentos foi selecionado como o valor de K no qual a redução da variância se estabilizou, resultando em agrupamentos compactos e bem separados.

9. Cálculo da variância do cluster e armazenamento em_{V lista}

Uma vez formados agrupamentos estáveis, o algoritmo calcula a variância do cluster para medir a compacidade de cada cluster. A variância_{V kj} para um dado cluster é determinada usando as distâncias entre cada ponto de dados no cluster e o centróide do cluster:

onde: x representa uma amostra de expressão gênica, C_i representa um agrupamento, C_ci é o centroide do cluster C_i, V_kj representa a variância registrada para a j^- ésima iteração com k clusters.

Essa variância é armazenada em uma lista V_, que será usada posteriormente para determinar o número ótimo de clusters.

10. Determinando o Número Ótimo de Clusters

Para encontrar o número ótimo de clusters K, o algoritmo realiza múltiplas iterações, observando diferentes condições iniciais. Os passos principais incluem:

O algoritmo primeiro identificou o valor mínimo da variância a partir da lista de variâncias calculadas para diferentes valores de K. A redução da variância entre contagens sucessivas de agrupamentos foi então medida usando a expressão ΔV=∣V_k−V_k−1∣, onde V_k denotava a variância para K clusters e V_k−1 representava a variância para K−1 clusters. Se a redução ΔV caísse abaixo do limiar pré-definido, indicando uma melhora negligenciável no agrupamento, o procedimento era encerrado. Caso contrário, o número de clusters era incrementado e o cálculo era repetido até que a contagem ótima de clusters fosse alcançada.

11. Finalização de Clusters para Classificação de Câncer e Não Câncer

Uma vez determinado o número ótimo de clusters K , o conjunto final de clusters representa grupos distintos dentro dos dados de expressão gênica. Normalmente, o algoritmo resulta em dois clusters principais:

Um cluster representando células cancerígenas (marcadas por assinaturas de expressão gênica distintas associadas à malignidade).

Um cluster representando células não cancerosas (contendo perfis normais de expressão gênica).

Os parâmetros, variáveis e constantes empregados no algoritmo proposto de clustering Quântico K-Means estão listados na Tabela 1. Defina as dimensões do conjunto de dados, defina o número de clusters K e aplique critérios de parada e limiares de otimização para guiar o processo. Configure configurações computacionais, como o número de disparos por execução e sementes aleatórias, para garantir a reprodutibilidade. Inicialize os centroides usando um método de seleção baseado em probabilidade e atualize-os iterativamente até a convergência. A tabela também especifica os resultados esperados, incluindo rótulos de clusters, centróides, K ótimo, métricas de avaliação e gráficos de visualização.

Categoria	Parâmetro	Valor / Padrão	Notas
Conjunto de dados	Conjunto de dados sobre câncer de mama	569 amostras × 32 recursos (reduzidos a 2 componentes PCA)	Redução da dimensionalidade com PCA
Número de aglomerados	K	Dinâmica, inicialmente 1, até 5	Otimizado usando redução de variância
Aglomerados máximos	Kmax	5	Limite superior para busca
Tacadas por corrida	N	1024	Medições por execução de circuito
Tolerância de parada	ε	1 × 10^-14	Critério de convergência de variância
Limiar de inclinação de variância	ΔV	9,9 × 10^-4	Limiar de parada para otimização
Observações	Mobsrv	3	Execuções independentes por tamanho de cluster
Limite de iteração	–	10	Passos máximos de atualização do centroide por execução
Semente aleatória	–	42	Garante a reprodutibilidade
Saídas esperadas	–	Rótulos de clusters, centróides, K ótimo, métricas de avaliação, gráficos	Exportado como arquivos .csv e .png
Variâncias entre agrupamentos	Vlist	vazio	Detecta o ótimo K
Centroide j	CJ	inicializado por função (baseado em probabilidades proporcionais às distâncias ao quadrado dos pontos)	Atualizado iterativamente e armazenar os centroides finais

Tabela 1: Materiais, Software e Configurações de Reprodutibilidade

Passo	Função / API (do seu código)	Ação	Desfecho Esperado
Codificação de características	QC.U(theta, pi, pi, qubit)	Codificar característica clássica normalizada em rotação de qubits	Estado do qubit
Teste SWAP / distância quântica	get_Distance(x, y) usando qc.cswap()	Construir circuito de 3 qubits (ancilla + dois estados)	Idêntico → P(0) ≈ 1.0; → ortogonal P(0) ≈ 0,5
Execução em circuitos	SamplerV2 com AerSimulator (1024 disparos)	Execute o circuito no simulador com transpilação (nível opt 1)	Distribuição de probabilidade para qubit ancilla
Inicialização do centroide	initialize_centroids_kmeans_pp(aponta, k)	Selecione centróides iniciais proporcionais à distância	Centroides iniciais diversos
Reatribuição de cluster	find_nearest_neighbour(aponta, centróides)	Atribuir pontos ao centroide mais próximo	Membros estáveis de clusters
Cálculo de variância	calculate_variance(centra, centers_distance)	Calcular a variância intra-cluster	A variância diminui a cada iteração
Inclinação de variância	grad_slope(k, V_k, k-1, V_k-1)	Compare ΔV com ε = 1e-14 e limiar de inclinação ΔV ≤ 0,000099	K ótimo detectado
Visualização	matplotlib.pyplot, plot_histogram	Atribuições de clusters de plotas e resultados quânticos	Diagramas de dispersão PCA, gráficos de variância, histogramas
Cálculo métrico	silhouette_score, calinski_harabasz_score, davies_bouldin_score	Avaliar a qualidade do agrupamento	Silhouette ≈ 0,64, CH ≈ 766, DB ≈ 0,65

Tabela 2: Detalhes da Implementação Executável do Algoritmo Proposto.

Implementação e Algoritmos

O Algoritmo Quântico K-Means com Determinação Ótima de Clusters é um método de agrupamento aprimorado por quantums que identifica dinamicamente o número ótimo de clusters enquanto emprega o mapeamento quântico^{de características 19} O procedimento começa considerando todos os pontos de dados como pertencentes a um único cluster. O número de clusters K então é progressivamente aumentado. Os centros de agrupamento são inicializados probabilisticamente de acordo com distâncias entre pontos, após as quais cada ponto de dados é atribuído ao seu centroide mais próximo, formando K agrupamentos. A variância do cluster é posteriormente calculada e os centroides são atualizados. Esse processo de reatribuição é repetido iterativamente até que não ocorram mais mudanças.

O algoritmo avalia a variância em múltiplas iterações, armazenando valores de variância correspondentes a diferentes contagens de clusters. O valor ótimo de K é determinado minimizando a variância enquanto se monitora a redução da variância ΔV. Se ΔV se tornar negligenciavelmente pequeno, o procedimento termina; caso contrário, K é incrementado e o processo de agrupamento é reiniciado. Essa estratégia adaptativa garante uma partição eficiente e precisa dos dados, especialmente em espaços de características de alta dimensão.

Figura 6: Fluxograma do procedimento proposto de Agrupamento Quântico Híbrido K-Means, mostrando mapeamento quântico de características, inicialização do centroide, atribuição iterativa de clusters, cálculo de variância quântica, verificação de convergência baseada em variância e seleção assistida por gradiente quântico do número ótimo de clusters. Por favor, clique aqui para ver uma versão ampliada desta figura.

As etapas a seguir descrevem o Algoritmo Quântico de K-Means para agrupar dados de expressão gênica de câncer e não cancerígeno.

Algoritmo: Agrupamento de Dados de Expressão Gênica de Células Cancerígenas e Não Cancerígenas usando o Algoritmo Quantum K-Means

Passo 1: Mapeamento de Características Quânticas (Codificação Multi Características).
Passo 2: Assumindo que inicialmente todos os pontos de dados pertencem ao mesmo cluster, então defina o valor de K=1 (Onde K: é o número de Clusters Ótimos, V: é a Variância do Cluster e ΔV: Redução da Variância).
Passo 3: Inicializar Centros (Escolhendo os Pontos Centrais Iniciais usando a proporção de probabilidade das distâncias entre os pontos de dados).
Passo 4: Atribua cada ponto de dados ao seu centroide mais próximo, que formará os clusters 'K' predefinidos.
Passo 5: Calcule a variância do cluster e coloque um novo centróide de cada cluster.
Passo 6: Repita o Passo 4, o que significa reatribuir cada ponto de dado ao novo centróide mais próximo de cada cluster.
Passo 7: Se houver alguma realocação, vá para o Passo 5 ou vá para o Passo 8.
Passo 8: Agora obtemos o cluster _{C j} ('j'ésima iteração com 'k' número de clusters) e calculamos a variância V_kj= , onde 'x': ponto de dados pertence ao cluster C_i, e C_ci: centroide de cluster do cluster C_i. Registre a variância V_kj na _lista V e comece novamente a agrupar com novos Centros do Passo 3 (Alguns números de vezes, ou seja, 'j' vezes, onde 1 ≤ j ≤ _{M obsrv}) com o mesmo 'K'.
Passo 9: Encontre a variância mínima V a_{partir da lista} V com 'K' número de clusters.
Passo 10: Calcule ΔV (ΔV = |V_k -_{V k-1}|, onde V_k: é a variância com 'K' número de clusters e V_k-1: é a variância com 'K-1' no de clusters), se ΔV for Otimizado Baseado em Gradiente Quântico (grande redução), então TERMINAR caso contrário aumente K (K=K+1) e vá para o Passo 3 com novo 'K'.
Passo 11: Os Clusters estão prontos e o número ótimo de clusters é 'K'.

Algoritmo de Mapeamento de Características Quânticas

Algoritmo 1: Mapeamento de Características Quânticas

Entradas: P aponta cada um dos estados quânticos |ψ〉 e |Φ〉
Saída: Uma estimativa de | 〈 ψ | Φ〉 |²
Etapas do algoritmo:
Passo 1: Pegamos um qubit e o inicializamos por zero; Aplique a porta de Hadamard e a rotative da base Z para o eixo X.
Step 2: Definimos φ (0 ≤ φ ≤ π ) em radian de acordo com o valor do ponto de dados em relação à característica 1.
φ = 2*rad(^cos-1)(d₀)), onde d₀ representa os valores de dados da característica 1 e d₀ ∈ [0, 1].
Passo 3: Definimos θ (0 ≤ θ ≤ π ) em radian, de acordo com o valor do ponto de dados em relação à característica 2.
θ = 2 * rad(^cos-1(d₁)), onde d₁ representa os valores de dados das características 2 e d₁ ∈ [0, 1].
Passo 4: Usamos a porta quântica U3 para implementar as rotações ao codificar as características dos pontos de dados.

Isso gira o qubit Φ radian em relação ao eixo x positivo e θ radian em relação ao eixo z positivo.

Comparação do Algoritmo de Estados Quânticos

Algoritmo 2: Comparando Estados Quânticos

Entradas: Dois qubits, |_{q 1}〉 e |q₂〉, cada um dos estados quânticos |ψ〉 e |Φ〉
Saída: Uma estimativa de | 〈ψ|Φ〉 |²
Etapas do algoritmo:
Passo 1: Considerar o qubit A como ancilla e inicializá-lo pelo estado |0〉
Passo 2: Aplicar a porta de Hadamard no qubit A
Passo 3: Aplicar o CSWAP no qubit |_{q 1} 〉 e |q₂ 〉 (no estado|ψ〉 e |Φ〉), com A como qubit de controle
Passo 4: Aplicar a porta de Hadamard no qubit A
Passo 5: Meça A em com base em Z e registre o resultado da medição como M
retorno M como nossa estimativa de | 〈 ψ|Φ 〉 |²

Algoritmo de Estimador de Distância Quântica para k-médias-agrupamento

Algoritmo 3: Estimador de Distância Quântica e Escolha do Novo Centroide de Cluster

Entradas: P no de pontos de dados e K no de centróides de cluster, cada um dos estados quânticos |ψ〉 e |Φ〉
Saída: Novo centróide agrupado associado aos pontos de dados
Etapas do algoritmo:
para i em variando de 1 a P:
Escolha^o ponto de dados e registre no |_{q i} 〉
para j em intervalo de 1 a K:
Escolha j^o centro agrupado e defina em |_{q j} 〉
Compare Estados Quânticos |q_i 〉 e |q_j 〉 ou seja, i^ésimo qubit^{com j} ésimo centróide e registrar a medição em M como (_{M i}, j)
fim para
Encontre a distância mínima (M_min , min) de M e defina min como o novo centróide de |q_i 〉 e gravar como C_i
fim para
retorno C como nossa nova lista de centroides

M= lista de todas as distâncias centróides agrupadas de |_{q i} 〉 i-ésimo qubit
C = lista de todos os centróides clusterizados de distância mínima recém-calculados C_i de |q_i 〉; ∀_{(i∈{1,...,P})}

Algoritmo de Seleção do Centroide Inicial

Algoritmo 4: Calcule pontos centrides iniciais usando a proporção de probabilidade das distâncias entre os pontos de dados

Entradas: m número de pontos de dados (X₁, X₂,...,X_m), cada um dos estados quânticos |ψ〉 e |Φ〉
Saída: retorne um conjunto S com K centróides iniciais
Etapas do algoritmo:
Passo 1: Escolha um ponto X aleatoriamente a partir dos pontos de dados X_i (1 ≤ i ≤ m) e adicione-o ao conjunto S
Passo 2: Para todo X_i, calcule a distância entre X_i usando o Estimador de Distância Quântica e o ponto centróide mais próximo em S e defina a distância como_{D dist}(X_i)
Passo 3: Escolha um número Y uniformemente entre 0 e D_dist(_{X 1})² + D_dist (X₂)² + ...+ D_dist (_{X m})²
Passo 4: Encontre um inteiro único i tal que
D_dist (X₁)² + D_dist (X₂)² + ...+ D_dist (X_i)² >= Y >_{D dist} (X₁)² + D_dist (X₂)² + ...+ D_dist (X_i-1)²
Passo 5: Adicionar X_i a S
Passo 6: Até que os centróides K sejam encontrados, repita os Passos 2 – 4

retorno S como os pontos centróides iniciais

Algoritmo de Cálculo de Variância Quântica

Algoritmo 5: Calcular a Variância Quântica

Entradas: P no de pontos de dados, cada um dos estados quânticos | ψ〉 e |Φ〉
Saída: retorne a variância dos pontos de dados
Etapas do algoritmo:
totalVariância ← 0
para i em variando de 1 a K:
Escolha^o centro agrupado e coloque em |q_i 〉
totalVariancei ← 0, M ← 0
para todo o J ∈ P, associado ao centroide do cluster i:
Escolha j^o ponto de dados e defina em |_{q j} 〉
Compare Estados Quânticos |q_i 〉 e |q_j 〉 ou seja, i^o centróide^{com j} ésimo ponto de dados e registrar a medição em_{M j}
M ← M + Mj
fim para
_{totalVariância i} ← [C_i é^{o i} agrupamento; |C_i | não é de pontos de dados no i^aglomerado, D_k é o ponto de dados ∈ C_i &_{M k}
é a distância entre o centróide de C_i e_{D k}]
totalVariância ← totalVariância + totalVariância
fim para
retorno total Variância

Algoritmo de Otimização Baseado em Gradiente Quântico (Obtendo o número ótimo de clusters)

A etapa de otimização baseada em gradiente quântico determina o número ótimo de clusters monitorando como a variância intra-cluster muda à medida que K aumenta. Calcule a variância para valores consecutivos de K e avalie a variação entre eles. Quando a redução da variância cai abaixo do limite predefinido, agrupamentos adicionais não melhoram mais a compacidade, e o correspondente K é selecionado como ideal. Esse critério baseado em curvatura garante que o agrupamento pare no ponto onde a estrutura natural dos dados é capturada sem superparticionamento.

Algoritmo 6: Otimização Baseada em Gradiente Quântico

Entradas:
Um circuito quântico parametrizado QC(θ) com uma porta de rotação de um único qubit_{R Y}(θ).
Um observável quântico = Z (valor esperado de Pauli-Z).
Uma faixa de valores de parâmetros θ.
Saída: A segunda derivada f′′(θ) do valor esperado 〈Z〉 em relação a θ.
Etapas do algoritmo:
Passo 1: Inicialize um circuito quântico de qubit único QC(θ) com:
Uma porta de rotação parametrizada R_Y(θ).
Medição na base computacional (Z).
Passo 2: Defina a função Evaluate_ Expectativa(θ), ou seja, f′(θ) =
Vincule o parâmetro θ ao circuito.
Execute o circuito em um simulador quântico com N disparos.
Meça as probabilidades de resultado P(0) e P(1).
Calcular valor esperado:
f(θ)=P(0)−P(1)
Passo 3: Calcule a Segunda Derivada usando a Regra do Deslocamento de Parâmetro:
Defina o valor de deslocamento s =
Calcule valores esperados em pontos deslocados:
f(θ+s), f(θ), f(θ−s)
Calcule a segunda derivada:
f ′′(θ) =
Passo 4: f ′′(θ) para analisar o comportamento de redução da variância.

Os detalhes de implementação da abordagem proposta de agrupamento quântico são fornecidos na Tabela 2. A tabela especifica as funções executáveis e APIs usadas em cada estágio do algoritmo, incluindo codificação de características em circuitos quânticos, execução do teste SWAP para estimativa de distância, inicialização do centroide, reatribuição iterativa de cluster e avaliação de variância/ΔV. Parâmetros de execução de circuitos, como o uso do SamplerV2 com o backend AerSimulator em 1024 tiros e o nível 1 de otimização de transpilação, também estão listados. Além disso, a tabela descreve os métodos de visualização aplicados para gerar diagramas de scatter PCA, gráficos de variância e histogramas, bem como as métricas de avaliação de agrupamento (silhouette_score, calinski_harabasz_score e davies_bouldin_score). Ao detalhar funções específicas em nível de comando e APIs, a tabela garante a reprodutibilidade de todas as etapas computacionais no algoritmo proposto.

Resultados

Um bom agrupamento dependerá de vários fatores, como distância de separação entre aglomerados, dentro da distância do aglomerado, critério de razão de variância, etc. Assim, o desempenho em Clustering foi avaliado usando três índices padrão: o Score Silhouette, o Índice Calinski-Harabasz (Índice CH) e o Índice Davies-Bouldin (Índice DB). A Pontuação de Silhueta mede a se...

Discussão

Este estudo propõe um novo Algoritmo Híbrido de Clustering Quântico K-Means com Detecção Ótima de Clusters, projetado especificamente para classificar amostras cancerosas e não cancerosas usando dados de expressão gênica de alta dimensão. A abordagem integra Mapeamento Quântico Multi-Característico, estimativa de distância quântica baseada em Teste de Troca e Otimização Baseada em Gradiente Quântico para determinar dinamicamente o número ótimo de clusters. Diferentemente...

Materiais

Lista de materiais utilizados neste artigo

Nome	Empresa	Número de catálogo	Comentários
Apple MacBook Pro (chip M1)	Apple Inc.	-	8 CPU core / GPU 8 core, 16? GB memória unificada — Usado para simulação local
Conjunto de Dados de Expressão Gênica para Câncer de Mama	Kaggle	-	Conjunto de dados com 569 amostras, 32 características (reduzidas via PCA no estudo)
macOS Monterey (Sistema Operacional)	Apple Inc.	12.6.9	Ambiente de execução usado em máquinas locais
matemática (biblioteca padrão em Python)	Fundação de Software Python	Embutidos	Funções matemáticas básicas
Matplotlib	Comunidade Matplotlib	3.8.4	Plotagem e visualização
NoiseModel, QuantumError, ReadoutError (Qiskit Aer)	Projeto IBM / Qiskit	parte do Aer 0.13.3	Usado para simular ruído quântico realista
NumPy	Desenvolvedores NumPy	1.26.4	Operações numéricas e manipulação de arrays
Pandas	Equipe de desenvolvimento do Pandas	2.2.2	Tratamento de dados, E/S, operações tabulares
Python	Fundação de Software Python	3.10.12	Linguagem de programação, usada no ambiente Jupyter / IPython
Qiskit Aer	Projeto IBM / Qiskit	0.13.3	Backend de simulador, com modelagem e execução de ruído
Qiskit IBM Runtime & ndash; Session, SamplerV2	Projeto IBM / Qiskit	0.41.1	Estrutura de execução para circuitos no simulador
Qiskit Terra	Projeto IBM / Qiskit	0.45.0	Estrutura quântica para construção e transpilação de circuitos
scikit-learn	Desenvolvedores scikit-learn	1.4.2	PCA, métricas de clustering, pré-processamento de dados