Approccio bioinformatico alla previsione del cancro utilizzando l'algoritmo di clustering quantistico per la similarità comportamentale nell'espressione genica

Sommario

Questo protocollo mira a clusterizzare i dati di espressione genica per la classificazione del cancro utilizzando un algoritmo Hybrid Quantum K-Means che rileva automaticamente il numero ottimale di cluster e li separa in modo efficiente, facendo avanzare le applicazioni bioinformatiche sui dispositivi Noisy Intermediate-Scale Quantum (NISQ).

Abstract

Questo studio introduce un algoritmo ibrido di clustering quantistico K-Means con rilevamento automatico dei cluster per classificare dati di espressione genica cancerosa e non cancerosa. Il metodo impiega la mappatura quantistica multi-caratteristica per la codifica degli stati, la stima quantistica basata su test di swap e l'ottimizzazione basata su gradiente quantistico per identificare dinamicamente il numero ottimale di cluster minimizzando la varianza intra-cluster. I centroidi iniziali sono selezionati tramite una strategia probabilità-proporzionale della distanza, migliorando stabilità e accuratezza. Applicato ai dataset sul cancro al seno, l'approccio supera l'algoritmo quantistico K-Means esistente, raggiungendo un punteggio Silhouette di 0,641 (rispetto a 0,601), un indice Calinski-Harabasz di 766,57 (rispetto a 617,65) e un indice Davies-Bouldin di 0,659 (rispetto a 0,704). Questi risultati indicano una superiore compattezza e separazione del cluster. Sebbene l'algoritmo proposto presenti una complessità temporale O leggermente superiore (N×_{K max}×_{M obs}) grazie all'ottimizzazione iterativa, supera significativamente le K medie quantistiche predefinite in termini di precisione di clustering, riduzione degli errori e fattibilità pratica. La sua efficienza nella gestione di dati ad alta dimensione e la resilienza al rumore quantistico ne evidenziano il potenziale per applicazioni bioinformatiche reali, in particolare nella classificazione del cancro tramite profili di espressione genica.

Introduzione

In ingegneria biomedica, bioinformatica, statistica, scienze sociali ed economia, il clustering è una tecnica fondamentale per organizzare i dati in gruppi omogenei significativi. Ad esempio, l'analisi dei dati topologici (TDA) è stata applicata ai dataset di espressione genica del cancro per rivelare modelli strutturali in spazi ad alta^{dimensione 1}, il clustering organizza i dati in modo che oggetti con alta somiglianza siano posizionati nello stesso cluster, mentre oggetti dissimili siano assegnati a cluster diversi. Questo rientra nell'apprendimento non supervisionato e non richiede dati di addestramento etichettati.

Negli ultimi decenni sono stati sviluppati numerosi algoritmi di clustering. Gli approcci classici includono il clustering basato sulla^{partizione 2}˒³, il clustering basato sulla^{densità 4,5}, il clustering gerarchico ^6,7, il clustering basato su griglia⁸˒⁹ e il clustering basato su modelli¹⁰. Le recensioni di questi metodi ne evidenziano i punti di forza ma anche i loro limiti¹¹. Sebbene efficaci in contesti specifici, la maggior parte degli algoritmi classici fatica con dati ad alta dimensione, rumorosi o distribuiti in modo irregolare. Di conseguenza, non esiste un metodo universale di clustering che funzioni in modo ottimale su tutti i tipi di dati.

Per affrontare queste sfide, il clustering quantistico è emerso come un'alternativa promettente¹². A differenza degli algoritmi classici, gli approcci ispirati al quantismo sfruttano sovrapposizione, entanglement e altri principi della meccanica quantistica per esplorare gli spazi dati in modo più efficiente. Questo paradigma è diventato sempre più accettato all'interno della comunità di ricerca¹³˒¹⁴˒¹⁵˒¹⁶˒¹⁷˒¹⁸, poiché dimostra potenziali vantaggi rispetto al clustering classico nella gestione di dataset ad alta dimensione e rumorosi. Tuttavia, i metodi di clustering quantistico esistenti spesso soffrono di conteggi di cluster predefiniti o di inizializzazione instabile del centroide, che ne riducono la robustezza nelle applicazioni pratiche.

In questo lavoro viene introdotto un innovativo algoritmo ibrido di clustering quantistico K-Means basato su partizioni, che incorpora quattro innovazioni distinte: (i) Mappatura Quantistica Multi-Feature per codificare dati di espressione genica nello spazio di Hilbert ad alta dimensione; (ii) inizializzazione basata sulla quota di centroide proporzionale alla probabilità, migliorando la stabilità rispetto all'inizializzazione casuale; (iii) Stima quantistica basata su Swap Test per una misurazione accurata della somiglianza; e (iv) Ottimizzazione Basata sul Gradiente Quantistico per determinare dinamicamente il numero ottimale di cluster minimizzando la varianza intra-cluster. Questi contributi distinguono il metodo proposto dai precedenti approcci di clustering^{quantistico 19,20}, migliorando robustezza, scalabilità e applicabilità in scenari bioinformatici reali.

Raggruppare i dati sull'espressione genica è un compito fondamentale in bioinformatica, in particolare per distinguere tra cellule cancerose e non cancerose in base ai loro profili genetici. I metodi tradizionali di clustering, come i classici K-Means, spesso faticano con la natura ad alta dimensione dei dataset di espressione genica, portando a una classificazione subottimale. Per superare queste sfide, introduciamo l'Algoritmo Quantum K-Means con Determinazione Ottimale del Cluster, che sfrutta la mappatura quantistica delle caratteristiche e l'inizializzazione probabilistica del centroide per ottenere prestazioni di clustering superiori. Questo algoritmo non solo raggruppa efficacemente i dati sull'espressione genica, ma determina automaticamente anche il numero ottimale di cluster, consentendo l'identificazione di distinti sottotipi di cancro

L'algoritmo proposto viene applicato a dataset contenenti sia profili di espressione genica cancerosi che non cancerosi, raggruppandoli in base alla similarità comportamentale per valutarne l'efficacia.

Protocollo

1. Mappatura quantistica delle caratteristiche

La codifica dei punti dati classici in stati quantistici si ottiene mapponoli in uno spazio di Hilbert quantistico, che può essere accessibile e manipolato in modo efficiente da un computer^{quantistico 16}˒^17,19. Questo processo impiega una mappa quantistica di caratteristiche non lineare che incorpora dati classici nello spazio di Hilbert (Figura 1). Una mappa di caratteristiche di circuito quantistico fissa trasforma i punti dati di input in stati^{quantistici 17}, mentre i circuiti variazionali consentono compiti di machine learning adattando la base^{di misurazione 22}. Un circuito variazionale è costituito da un insieme di porte quantistiche parametrizzate, ottimizzate tramite tecniche ibride^{quantistico-classiche 23}.

Figura 1: Mappatura delle caratteristiche nello spazio di Hilbert quantistico. Clicca qui per visualizzare una versione più grande di questa figura.

2. Codifica del punto target e dei centroidi in qubit

Per codificare le caratteristiche dei nostri punti dati, dobbiamo eseguire rotazioni usando porte U3.

Questo ruota i radiani θ del qubit lontano dall'asse z positivo e i radiani Φ rispetto all'asse x positivo.

Tutti i qubit venivano inizializzati nello stato ∣0〉 prima che iniziasse il processo di codifica. Ogni valore di espressione genica è stato normalizzato all'intervallo [0,1] e convertito in un angolo di rotazione usando la relazione θ_i=πx_i. A ogni qubit veniva quindi applicata una porta unitaria parametrizzata per codificare la corrispondente caratteristica, implementata in Qiskit usando l'operazione qc.u(theta_i, pi, pi, qubit_index). Quando più caratteristiche venivano codificate, la procedura di rotazione veniva ripetuta tra i qubit appropriati per creare una rappresentazione multi-caratteristica. Dopo queste operazioni, lo stato quantistico risultante ∣ψ〉 rappresentava il vettore di caratteristiche codificato nello spazio di Hilbert. Non è stata effettuata alcuna misurazione durante questa fase, poiché lo stato preparato era riservato alla successiva stima della somiglianza.

3. Confronto degli Stati Quantistici

I risultati degli esperimenti quantistici sono intrinsecamente casuali perché i qubit sono instabili per natura, come descritto nella fisica quantistica. Di conseguenza, le conclusioni e le previsioni devono essere espresse in termini di probabilità e incertezze. Trarre conclusioni inequivocabili rappresenta quindi una vera sfida. Tuttavia, quando gli stati quantistici in considerazione sono puri, le differenze tra stati (con probabilità non nulla) possono essere previste in modo inequivocabile tramite^{sperimentazioni 24}˒²⁵.

Due stati quantistici, ∣ψ〉 e ∣φ〉, furono inizialmente caricati in registri quantistici separati. Un qubit ancilla veniva quindi inizializzato nello stato ∣0〉 per controllare l'operazione di swap. Un cancello Hadamard fu applicato all'ancilla per metterlo in sovrapposizione prima dell'esecuzione dell'operazione controllata SWAP. La porta Fredkin (CSWAP) utilizzava l'ancilla come qubit di controllo e i due registri dati come bersagli, consentendo interferenze tra gli stati. Dopo questa operazione, fu applicata una seconda porta di Hadamard all'ancilla per completare il pattern di interferenza. Veniva misurato solo il qubit ancilla, e il risultato della misura codificava la somiglianza tra i due stati. Quando gli stati erano identici, l'ancilla produceva l'esito 0 con probabilità 1, mentre gli stati ortogonali producevano l'esito 0 con probabilità 0,5.

Figura 2: Illustrazione del confronto basato sulla probabilità, se gli stati ρ e ξ sono diversi, allora la distribuzione di probabilità osservata appartiene a P_E⁻ \ P_E⁺. Clicca qui per visualizzare una versione più grande di questa figura.

L'operatore di densità ρ è associato a qualsiasi stato quantistico ρ ∈ S(H), tale che tr[ρ] = 1 e ρ ≥ 0. Qui, insieme di tutti gli stati S(H) di un sistema che sarà associato allo spazio di Hilbert H. La Misura Valorizzata da Operatori Positivi (POVM) è una misurazione delle caratteristiche statistiche quantistiche che è una raccolta di operatori positivi E₁, . . . ,_{E n} come E (che agiscono su H) e l'identità I = . Una distribuzione di probabilità assegna la misura E per ogni stato ρ ∈ S(H), dove p_j = tr[_{E j}ρ]≥ 0 e =^{1 26}.

4. Confronto degli Stati quantistici basato su SWAP

La differenza tra due stati quantistici può essere misurata utilizzando la procedura di test SWAP nel calcolo quantistico. Questo metodo è stato introdotto per la prima volta da Barenco et al.²⁷ anni e successivamente riscoperti da John Watrous, Ronald de Wolf, Harry Buhrman e Richard ^{Cleve 28}. Il test SWAP è stato applicato al calcolo quantistico e all'apprendimento automatico ^{quantistico 15, 29}.

Il test SWAP prende ∣ψ〉 e ∣φ〉 come stati di ingresso e produce 1 (una variabile casuale di Bernoulli) con probabilità 1/2 - 1/2〈φ,ψ〉² , che stima il prodotto scalare al quadrato dei due stati ³⁰.

Spiegazione del circuito

Consideriamo due stati ∣φ〉 e ∣ψ〉 del sistema, il protocollo all'inizio è ∣0,φ,ψ〉. Dopo l'applicazione della porta Hadamard, lo stato viene cambiato a ∣0,φ,ψ〉 + ∣1,φ,ψ〉. La porta CSWAP trasforma lo stato in (0,φ,ψ〉 + ∣1,ψ,φ〉). Dopo la seconda porta Hadamard, lo stato diventa 1/2(|0,φ,ψ〉 + ∣1,φ,ψ〉 + |0,ψ,φ〉 - ∣1,ψ,φ〉)= 1/2∣0〉(|φ,ψ〉 + |ψ,φ〉) +  1/2|1〉(|φ,ψ〉 - |ψ,φ〉). Il primo qubit viene quindi misurato, la probabilità di ottenere l'esito 0 è P(Primo qubit = 0) = 1/2 (〈φ|〈ψ| + 〈ψ|〈φ|) 1/2 (|φ,ψ〉 + |ψ,φ〉) = 1/2 + 1/2 |〈ψ|φ〉|². Se ψ e φ sono ortogonali (|〈ψ|ϕ〉|² = 0), allora la probabilità di ottenere 0 è 1/2. Se gli stati sono identici (|〈ψ|ϕ〉|² = 1) allora la probabilità di ottenere 0 è 1. ²⁴

Figura 3: (a) Circuito della porta di Fredkin con stato polarmente opposto, (b) Uscita del grafo misurato dalla probabilità, (c) Circuito della porta di Fredkin con porta di Hadamard, (d) Uscita del grafo misurato dalla probabilità. Clicca qui per visualizzare una versione più grande di questa figura.

Il circuito utilizzava un qubit ancilla insieme a due registri che codificavano gli stati quantistici ∣ψ〉 e ∣φ〉. Tutti i qubit venivano inizializzati prima dell'inizio della fase di codifica. Le caratteristiche di espressione genica venivano quindi codificate nei rispettivi registri utilizzando la procedura di mappatura delle caratteristiche. Una porta di Hadamard veniva applicata al qubit ancilla per creare una sovrapposizione, dopo la quale veniva eseguita un'operazione controlled-SWAP tra i due registri di stato con l'ancilla come controllo. Una seconda porta di Hadamard fu applicata all'ancilla per completare il pattern di interferenza, e successivamente fu misurato il qubit ancilla. Quando i due stati codificati erano identici, l'ancilla produceva costantemente il risultato 0. Quando gli stati erano ortogonali, l'ancilla produceva l'esito con probabilità 0,5. Per stati parzialmente simili, la probabilità di ottenere 0 era compresa tra 0,5 e 1, riflettendo il grado di somiglianza tra gli stati.

5. Stima quantistica della distanza

Nell'analisi dei dati classica, le distanze tra i punti dati possono essere calcolate direttamente usando misure come la distanza euclidea o di ^{Manhattan 2,3}. Nel caso dei qubit su un computer quantistico, questo compito è più complesso a causa della natura probabilistica degli stati quantistici. Sebbene differenze di fase e ampiezze di probabilità possano essere misurate, non possono essere rappresentate direttamente come distanze tra due vettori ^{24, 26}.

Per il clustering, è necessario valutare le posizioni relative dei punti dati rispetto ai centroidi^{cluster 13}. Per assegnare ogni qubit al cluster appropriato, deve essere definito un parametro che funga da indicatore della vicinanza al corrispondente centroide del cluster.

Per raggiungere questo risultato, viene introdotto un parametro che correla positivamente con la somiglianza, fungendo così da alternativa alle misure convenzionali di distanza ^15,30.

Il processo di stima della distanza iniziava con uno stato quantistico normalizzato ∣Ψ〉 e un qubit ausiliario inizializzato a zero ∣q₀〉. L'obiettivo era stimare la distanza tra il nuovo punto dati codificato in ∣_{q 1}〉 e un centroide cluster codificato in ∣q₂〉. Per preparare la sovrapposizione richiesta per il pattern di interferenza, fu applicata una porta di Hadamard al qubit ancilla, che produceva lo stato ( ∣0〉 + ∣1〉 ) ⊗ ∣Ψ〉 ). Veniva quindi applicata una porta controlled-SWAP (Fredkin) con l'ancilla come controllo, che intrecciava l'ancilla con i due stati codificati e permetteva alla loro sovrapposizione di influenzare l'esito della misurazione. Questa operazione produceva lo stato ( ∣0〉 ⊗ ∣Ψ〉 + ∣1〉 ⊗_{F swap}(∣Ψ〉) ), dal quale la distanza basata sul prodotto interno poteva essere estratta tramite misurazioni successive dell'ancilla.

Implementazione e uscita del circuito

Questo circuito quantistico codifica i dati di espressione genica in qubit usando la codifica di fase e successivamente confronta due stati di espressione genica tramite la porta Controlled-Swap (CSwap), nota anche come Swap^{Test 12}.

Per creare la sovrapposizione richiesta, le porte di Hadamard vengono applicate a tutti i qubit (q₀ a_{q 4}), risultando in una sovrapposizione uguale di tutti gli stati base |Ψ〉 = , Questa inizializzazione consente il calcolo parallelo su più valori di espressione genica. Ogni qubit subisce quindi una rotazione di fase, , dove θ_x corrisponde al valore di espressione genica mappato. Gli operatori unitari U(θ,π,π) applicati ai qubit q_{1-q 4} codificano i livelli di espressione dei singoli geni, con ogni angolo θ che rappresenta una versione trasformata dell'espressione di un gene. Questa procedura mappa dati biologici classici in stati quantistici tramite codifica di fase, permettendo di rappresentare più geni in uno spazio quantistico^{ad alta dimensione 6}.

Le porte CSwap vengono poi utilizzate per confrontare gli stati codificati tramite entangling. Il qubit ausiliario q₀ agisce come controllo, determinando se gli stati di q_{1-q 4} sono scambiati. Stati quantistici simili generano interferenza costruttiva in q₀, con conseguente probabilità maggiore di misurare ∣0〉. Al contrario, gli stati dissimili aumentano la probabilità di misurare ∣1〉. Una successiva porta di Hadamard su q₀ garantisce l'interferenza di ampiezza, consentendo l'estrazione di informazioni di similarità tramite la misurazione.

Supponiamo che due stati quantistici ∣ψ〉 e ∣φ〉 rappresentino dataset di espressione genica distinti, |ψ〉 = ∑i a_i |i〉, |φ〉 = ∑_ib_i |i〉 .

Il Swap Test valuta la fedeltà (prodotto interno) tra di essi:

P (0) = ,

Dove ∣〈ψ∣φ〉∣ indica il prodotto interno. Se P(0) ≈ 1, gli stati sono simili; se P(0) ≈ 0,5 o inferiore, sono dissimili.

Questo quadro consente il confronto di insiemi di dati tra pazienti o condizioni sperimentali (ad esempio, tessuto normale vs. malato). Fornisce una base efficiente per il clustering di dati ad alta dimensione all'interno di modelli di apprendimento automatico quantistico. Il Test di Swap supporta l'identificazione di somiglianze tra stati quantistici, che possono essere utilizzate per raggruppare campioni in cluster^{significativi 4}.

Figura 4: Circuito di misurazione della distanza tra punti dati e centroidi. Clicca qui per visualizzare una versione più grande di questa figura.

Figura 5: Output del grafico misurato per probabilità. Clicca qui per visualizzare una versione più grande di questa figura.

Un punto dati veniva prima codificato nello stato quantistico ∣ψ〉 e il corrispondente centroide del cluster veniva codificato nello stato ∣φ〉. La procedura di prova dello swap descritta in precedenza è stata poi eseguita per confrontare questi due stati, e la probabilità di misurazione ancilla P(0) è stata registrata. La fedeltà tra gli stati fu ottenuta come F=∣〈ψ∣φ〉∣², e la distanza quantistica fu definita come D (ψ,φ) = . Un valore minore di D indicava che il punto dati era più vicino al centroide nello spazio delle caratteristiche quantistiche.

6. Selezione iniziale del centroide

L'inizializzazione dei centroidi cluster è fondamentale per la stabilità e l'accuratezza del clustering K-Means. La selezione randomizzata può produrre centroidi mal distribuiti, portando a una convergenza lenta e risultati subottimali. Per affrontare questo problema, viene utilizzato un metodo probabilità-distanza proporzionale ispirato alla strategia^{K-Means++ 20} . Nell'approccio potenziato quantistico, le distanze vengono valutate utilizzando il Quantum Distance Estimator basato sul test SWAP, assicurando che i centroidi selezionati rappresentino meglio la distribuzione dei dati sottostante. Questa strategia migliora la separazione dei cluster e la robustezza algoritmica, in particolare nei dataset ad alta dimensione.

Il processo di inizializzazione del centroide iniziava selezionando casualmente un punto dati per fungere da primo centroide. La distanza quantistica tra questo baricentroide e ogni punto dati rimanente veniva poi calcolata utilizzando la procedura di stima quantistica della distanza. Sulla base di questi valori di distanza, è stata creata una distribuzione di probabilità in cui a ogni punto veniva assegnata una probabilità di selezione proporzionale alla distanza al quadrato dal centroide più vicino. Nuovi centroidi venivano campionati secondo questa distribuzione e la procedura veniva ripetuta fino a ottenere il numero desiderato di centroidi K. Questo approccio produsse un insieme iniziale di centroide con una separazione sostanzialmente migliore rispetto alla selezione casuale.

7. Calcolo della varianza quantistica

La varianza di cluster quantifica la compattezza dei punti dati attorno ai loro centroidi, rendendola una metrica cruciale per valutare la qualità del clustering. Nelle K-Means classiche, la varianza viene calcolata come la distanza media quadratica tra i punti dati e i loro baricentroi assegnati. Nell'approccio quantum-enhancement, queste distanze vengono ottenute utilizzando il Quantum Distance Estimator (tramite il test SWAP), che calcola le somiglianze basate sulla fedeltà tra stati quantistici. Sommando le distanze quadrate all'interno di ciascun cluster e normalizzando per dimensione del cluster, otteniamo un valore di varianza che riflette il grado di coesione intra-cluster. Minimizzare questa varianza garantisce cluster più stretti e significativi, cosa particolarmente importante nei dataset di espressione genica ad alta dimensione per distinguere campioni cancerosi e non cancerosi.

L'assegnazione del cluster veniva eseguita assegnando ogni punto dati quantistico codificato al centroide più vicino tramite la stima quantistica della distanza. Per ogni cluster C_k, veniva calcolata la distanza quantistica D(ψ_{i,C k}) tra ogni punto dati e il suo centroide. La varianza all'interno del cluster veniva poi calcolata usando , che misurava la compattezza di ciascun cluster. La varianza totale è stata ottenuta sommando le singole varianze su tutti i cluster. Questo valore totale di varianza è stato registrato per determinare il numero ottimale di cluster e per valutare la performance complessiva del clustering.

8. Ottimizzazione basata su gradiente quantistico

Determinare il numero ottimale di cluster (K) è una sfida fondamentale nei compiti di clustering. Le K-Means tradizionali richiedono che K sia predefinito, spesso portando a un sotto- o sovra-clustering. Nel nostro approccio potenziato quantisticamente, integriamo l'Ottimizzazione Basata sul Gradiente Quantistico (QGBO) per identificare in modo adattivo il conteggio ottimale del cluster. L'algoritmo aumenta iterativamente K, ricalcola la varianza ad ogni passaggio e valuta la riduzione della varianza (ΔV). Quando i miglioramenti nella varianza scendono sotto una soglia, il clustering viene terminato. Il gradiente quantistico viene calcolato utilizzando la regola dello spostamento dei parametri, che stima le derivate dei valori attesi dai circuiti quantistici. Questo approccio garantisce che il numero finale di cluster bilanci precisione ed efficienza, rendendolo particolarmente utile nelle applicazioni bioinformatiche dove il numero reale di sottotipi biologici non è noto in anticipo.

Il processo di clustering iniziava con K=1, e la varianza totale V(K) veniva calcolata utilizzando la procedura di calcolo della varianza quantistica. Il numero di cluster fu quindi aumentato a K+1 e la varianza V(K+1) fu ricalcolata. La riduzione della varianza, ΔV=V(K)−V(K+1), è stata valutata per determinare se ulteriori cluster continuassero a migliorare la compattezza dei dati. L'iterazione si è interrotta quando ΔV è sceso sotto la soglia predefinita, indicando che ulteriori aumenti di K non hanno prodotto miglioramenti significativi. È stato costruito un circuito quantistico parametrizzato con porte variazionali per monitorare i cambiamenti di curvatura nella tendenza della varianza, e queste informazioni hanno guidato il processo di ottimizzazione del cluster. Il numero ottimale di cluster è stato selezionato come il valore di K al quale la riduzione della varianza si stabilizzava, risultando in cluster compatti e ben separati.

9. Calcolo della varianza del cluster e memorizzazione in_{V list}

Una volta formati cluster stabili, l'algoritmo calcola la varianza del cluster per misurare la compattezza di ciascun cluster. La varianza_{V kj} per un dato cluster è determinata utilizzando le distanze tra ciascun punto dati nel cluster e il centroide del cluster:

dove: x rappresenta un campione di espressione genica, C_i rappresenta un cluster, C_ci è il baricentroide del cluster C_i, V_kj rappresenta la varianza registrata per la j^iterazione con k cluster.

Questa varianza viene memorizzata in una lista V_, che sarà poi utilizzata per determinare il numero ottimale di cluster.

10. Determinazione del numero ottimale di cluster

Per trovare il numero ottimale di cluster K, l'algoritmo esegue più iterazioni, osservando diverse condizioni di partenza. I passaggi chiave includono:

L'algoritmo identificò innanzitutto il valore minimo della varianza dall'elenco delle varianze calcolate per diversi valori di K. La riduzione della varianza tra i conteggi di cluster successivi è stata quindi misurata usando l'espressione ΔV=∣V_k−V_k−1∣, dove V_k indicava la varianza per K cluster e V_k−1 rappresentava la varianza per K−1 cluster. Se la riduzione ΔV scendeva sotto la soglia predefinita, indicando un miglioramento trascurabile nel clustering, la procedura terminava. Altrimenti, il numero di cluster veniva incrementato e il calcolo veniva ripetuto fino a raggiungere il numero ottimale di cluster.

11. Finalizzazione dei cluster per la classificazione del cancro e non cancro

Una volta determinato il numero ottimale di cluster K , l'insieme finale di cluster rappresenta gruppi distinti all'interno dei dati di espressione genica. Tipicamente, l'algoritmo produce due cluster primari:

Un cluster rappresenta cellule cancerose (caratterizzate da firme di espressione genica distinte associate a malignità).

Un cluster rappresenta cellule non cancerose (contenenti profili di espressione genica normali).

I parametri, le variabili e le costanti impiegati nell'algoritmo proposto di clustering Quantum K-Means sono elencati nella Tabella 1. Definire le dimensioni del dataset, impostare il numero di cluster K e applicare criteri di arresto e soglie di ottimizzazione per guidare il processo. Configura le impostazioni computazionali come il numero di colpi per run e seed casuali per garantire la riproducibilità. Inizializzare i centroidi usando un metodo di selezione basato sulla probabilità e aggiornarli iterativamente fino alla convergenza. La tabella specifica anche i risultati attesi, inclusi etichette di cluster, centroidi, K ottimale, metriche di valutazione e grafici di visualizzazione.

Categoria	Parametro	Valore / Predefinito	Note
Dataset	Dataset sul cancro al seno	569 campioni × 32 caratteristiche (ridotte a 2 componenti PCA)	Dimensionalità ridotta con PCA
Numero di cluster	Okay	Dinamico, inizialmente 1, fino a 5	Ottimizzato usando la riduzione della varianza
Cluster massimi	Kmax	5	Limite superiore per la ricerca
Tiri per punto	N	1024	Misurazioni per esecuzione del circuito
Tolleranza di arresto	ε	1 × 10^-14	Criterio di convergenza della varianza
Soglia di pendenza di varianza	ΔV	9.9 × 10^-4	Soglia di stop per l'ottimizzazione
Osservazioni	Mobsrv	3	Esercizi indipendenti per dimensione di cluster
Limite di iterazione	–	10	Passi massimi di aggiornamento del centroide per esecuzione
Seme casuale	–	42	Garantisce la riproducibilità
Risultati attesi	–	Etichette di cluster, centroidi, K ottimale, metriche di valutazione, grafici	Esportati come file .csv e .png
Varianze tra cluster	Vlist	vuoto	Rileva K ottimale
Centroide j	CJ	inizializzato tramite funzione (basato sulle probabilità proporzionali alle distanze al quadrato dei punti)	Aggiornato iterativamente e e conserva i centroidi finali

Tabella 1: Materiali, Software e Impostazioni di Riproducibilità

Passo	Funzione / API (dal tuo codice)	Azione	Esito atteso
Codifica delle caratteristiche	qc.u(theta, pi, pi, qubit)	Codificare la caratteristica classica normalizzata nella rotazione dei qubit	Stato dei qubit
Test SWAP / distanza quantistica	get_Distance(x, y) usando qc.cswap()	Costruzione di circuito a 3 qubit (ancilla + due stati)	Identico → P(0) ≈ 1.0; → ortogonale P(0) ≈ 0,5
Esecuzione del circuito	SamplerV2 con AerSimulator (1024 riprese)	Eseguire il circuito sul simulatore con traspilazione (opt livello 1)	Distribuzione di probabilità per il qubit ancilla
Inizializzazione del centroide	initialize_centroids_kmeans_pp(indica, k)	Seleziona i centroidi iniziali proporzionali alla distanza	Centroidi di partenza diversi
Riassegnazione del cluster	find_nearest_neighbour(indica, centroidi)	Assegnare i punti al centroide più vicino	Appartenenze stabili al cluster
Calcolo della varianza	calculate_variance(al centro, centers_distance)	Calcolo la varianza intra-cluster	La varianza diminuisce ad ogni iterazione
Pendenza di varianza	grad_slope(k, V_k, k-1, V_k-1)	Confronta ΔV con ε = 1e-14 e soglia di pendenza ΔV ≤ 0,000099	K ottimale rilevato
Visualizzazione	matplotlib.pyplot, plot_histogram	Assegnazioni di cluster e risultati quantistici	Diagrammi di scatter PCA, grafici di varianza, istogrammi
Calcolo metrico	silhouette_score, calinski_harabasz_score, davies_bouldin_score	Valutare la qualità del clustering	Silhouette ≈ 0,64, CH ≈ 766, DB ≈ 0,65

Tabella 2: Dettagli di implementazione eseguibili dell'algoritmo proposto.

Implementazione e algoritmi

L'Algoritmo Quantum K-Means con Determinazione Ottimale del Cluster è un metodo di clustering potenziato dal livello quantistico che identifica dinamicamente il numero ottimale di cluster impiegando la mappatura quantistica delle caratteristiche¹⁹ La procedura inizia considerando tutti i punti dati come appartenenti a un singolo cluster. Il numero di cluster K aumenta progressivamente. I centri di cluster sono inizializzati probabilisticamente secondo le distanze inter-punti, dopo di che ogni punto dati viene assegnato al suo baricentroide più vicino, formando K cluster. La varianza del cluster viene successivamente calcolata e i centroidi vengono aggiornati. Questo processo di riassegnazione viene ripetuto iterativamente finché non si verificano ulteriori cambiamenti.

L'algoritmo valuta la varianza su più iterazioni, memorizzando valori di varianza corrispondenti a diversi conteggi di cluster. Il valore ottimale di K è determinato minimizzando la varianza mentre si monitora la riduzione della varianza ΔV. Se ΔV diventa trascurabilmente piccolo, la procedura termina; altrimenti, K viene incrementato e il processo di clustering riavvia. Questa strategia adattiva garantisce una partizione efficiente e accurata dei dati, in particolare negli spazi di caratteristiche ad alta dimensione.

Figura 6: Diagramma di flusso della procedura proposta di Hybrid Quantum K-Means Clustering, che mostra la mappatura quantistica delle caratteristiche, l'inizializzazione del centroide, l'assegnazione iterativa dei cluster, il calcolo della varianza quantistica, il controllo della convergenza basato sulla varianza e la selezione assistita dal gradiente quantistico del numero ottimale di cluster. Clicca qui per visualizzare una versione più grande di questa figura.

I passaggi seguenti delineano l'Algoritmo Quantistico K-Means per raggruppare dati di espressione genica del cancro e non del cancro.

Algoritmo: Clustering dei dati di espressione genica di cellule tumorali e non tumorali utilizzando l'algoritmo quantistico K-Means

Passo 1: Mappatura quantistica delle caratteristiche (codifica multi-caratteristica).
Passo 2: Assumendo che inizialmente tutti i punti dati appartengano allo stesso cluster, si imposta il valore di K=1 (dove K: è il numero di cluster ottimali, V: è la varianza del cluster e ΔV: riduzione della varianza).
Passo 3: Inizializzare i Centri (Scegliere i Punti Centrali Iniziali usando la proporzione di probabilità delle distanze tra i punti dati).
Passo 4: Assegnare ogni punto dati al loro centroide più vicino, che formeranno i cluster 'K' predefiniti.
Passo 5: Calcola la varianza del cluster e posiziona un nuovo centroide per ciascun cluster.
Passo 6: Ripeti il Step-4, cioè riassegnare ogni punto dati al nuovo centroide più vicino di ogni cluster.
Passo 7: Se avviene qualche riassegnazione, allora vai al Passaggio 5 altrimenti vai al Passo 8.
Passo 8: Ora otteniamo il cluster _{C j} ('j'esima iterazione con 'k' numero di cluster) e calcoliamo la varianza V_kj= , dove 'x': il punto dati appartiene al cluster C_i, e C_ci: il centroide del cluster C_i. Tieni traccia della varianza V_kj nella lista V e ricomincia a raggruppare con nuovi Centri dal Passo 3 (poche volte no, cioè 'j', dove 1 ≤ j ≤ _{M obsrv}) con la stessa 'K'.
Passo 9: Trova la varianza minima V dalla_lista V con 'K' numero di cluster.
Passo 10: Calcolare ΔV (ΔV = |V_k -_{V k-1}|, dove V_k: è la varianza con 'K' numero di cluster e V_k-1: è la varianza con 'K-1' numero di cluster), se ΔV è Ottimizzato Basato sul Gradiente Quantistico (enorme riduzione) allora FINISH altrimenti aumenta K (K=K+1) e passa allo Passo 3 con la nuova 'K'.
Passo 11: I cluster sono pronti e il numero ottimale di cluster è 'K'.

Algoritmo di mappatura delle caratteristiche quantistiche

Algoritmo 1: Mappatura delle caratteristiche quantistiche

Input: P indica ciascuno degli stati quantistici |ψ〉 e |Φ〉
Output: Una stima di | 〈 ψ | Φ〉 |²
Passaggi dell'algoritmo:
Passo 1: Prendiamo un qubit e lo inizializziamo a zero; applicare la porta di Hadamard e ruotarla dalla base Z all'asse X.
Step 2: Impostiamo φ (0 ≤ φ ≤ π ) in radiano in base al valore del punto dati rispetto alla caratteristica 1.
φ = 2*rad(^cos-1)(d₀)), dove d₀ rappresenta i valori dati delle caratteristiche 1 e d₀ ∈ [0, 1].
Passo 3: Impostiamo θ (0 ≤ θ ≤ π ) in radiano in base al valore del punto dati rispetto alla caratteristica 2.
θ = 2 * rad(^cos-1(d₁)), dove d₁ rappresenta i valori dati delle caratteristiche 2 e d₁ ∈ [0, 1].
Passo 4: Usiamo la porta quantistica U3 per implementare le rotazioni eseguendo la codifica delle caratteristiche dei punti dati.

Questo ruota il qubit Φ radiano rispetto all'asse x positivo e θ radiano rispetto all'asse z positivo.

Confronto dell'algoritmo degli stati quantistici

Algoritmo 2: Confronto degli Stati Quantistici

Input: Due qubit |_{q 1}〉 e |q₂〉 ciascuno degli stati quantistici |ψ〉 e |Φ〉
Output: Una stima di | 〈ψ|Φ〉 |²
Passaggi dell'algoritmo:
Passo 1: Considerare il qubit A come ancilla e inizializzarlo per stato |0〉
Passo 2: Applica la porta di Hadamard sul qubit A
Passo 3: Applica CSWAP sul qubit |_{q 1} 〉 e |_{q 2} 〉 (sullo stato|ψ〉 e |Φ〉), con A come qubit di controllo
Passo 4: Applica la porta di Hadamard sul qubit A
Passo 5: Misura A in sulla base di Z e registra il risultato della misurazione come M
Ritorno M come la nostra stima di | 〈 ψ|Φ 〉 |²

Algoritmo di stimazione quantistica delle distanze per k-medie

Algoritmo 3: Stima della Distanza Quantistica e Scelta del nuovo Centroide del Cluster

Input: P numero di punti dati e K numero di centroidi di cluster, ciascuno degli stati quantistici |ψ〉 e |Φ〉
Output: Nuovo centroide clusterizzato associato ai punti dati
Passaggi dell'algoritmo:
per i in variazioni da 1 a P:
Prendi^{i il} punto dati e registralo su |_{q i} 〉
per j nell'intervallo da 1 a K:
Scegli j^il centroide clusterizzato e impostalo su |_{q j} 〉
Confronta gli Stati Quantistici |q_i 〉 e |q_j 〉 cioè i^th qubit con j^th centroide e registrare la misura in M come (_{M i}, j)
fine per
Trova la distanza minima (M min, min) da M e poni min come nuovo centroide di |q_i 〉 e registrarlo come C_i
fine per
Ritorno C come nuova lista di centroidi

M= elenco di tutte le distanze del centroide raggruppato da |_{q i} 〉 i-esimo qubit
C = elenco di tutti i nuovi centroide cluster a distanza_{minima C i} di |q_i 〉; ∀_{(i∈{1,...,P})}

Algoritmo di selezione iniziale del centroide

Algoritmo 4: Calcolare i punti centroide iniziali usando la proporzione di probabilità delle distanze tra i punti dati

Input: m numero di punti dati (X₁, X₂,...,X_m), ciascuno degli stati quantistici |ψ〉 e |Φ〉
Output: restituire un insieme S con K centroidi iniziali
Passaggi dell'algoritmo:
Passo 1: Scegli un punto X a caso dai dati X_i (1 ≤ i ≤ m) e aggiungilo all'insieme S
Passo 2: Per ogni X_i, calcola la distanza tra X_i usando lo Stmatizzatore di Distanza Quantistica e il punto centroide più vicino in S e imposta la distanza come_{D dist}(X_i)
Passo 3: Scegliere un numero Y uniformemente tra 0 e D_dist(_{X 1})² + D_dist (X₂)² + ...+ D_dist (X_m)²
Passo 4: Trovare un intero unico i tale che
D_dist (X₁)² + D_dist (X₂)² + ...+ D_dist (X_i)² >= Y > D_dist (X₁)² + D_dist (X₂)² + ...+ D_dist (X_i-1)²
Passo 5: Aggiungi X_i a S
Passo 6: Fino a quando non si trovano i centroidi K, ripeti i passaggi 2 – 4

Ritorno S come punti centroide iniziali

Algoritmo di calcolo della varianza quantistica

Algoritmo 5: Calcolare la varianza quantistica

Input: P numero di punti dati, ciascuno degli stati quantistici | ψ〉 e |Φ〉
Output: restituire la varianza dei punti dati
Passaggi dell'algoritmo:
totalVarianza ← 0
per i in variazioni da 1 a K:
Scegli^il centroide cluster e impostalo su |_{q i} 〉
totalVariancei ← 0, M ← 0
Per tutto il J ∈ P, associato al centroide cluster i:
Scegli j^il punto dati e impostalo su |_{q j} 〉
Confronta gli Stati Quantistici |q_i 〉 e |q_j 〉 cioè i^th centroid^{con j th} data point e registrare la misurazione in_{M j}
M ← M + Mj
fine per
totalVariance_i ← [C_i è il i cluster i^; |C_i | non è un punto dati^{nel i cluster}, D_k è il punto dati ∈ C_i &_{M k}
è la distanza tra il baricentroide di C_i e D_k]
totalVarianza ← totalVarianza + totaleVarianza
fine per
ritorno totale Varianza

Algoritmo di ottimizzazione basato su gradiente quantistico (Ottenere il numero ottimale di cluster)

Il passaggio di ottimizzazione basato sul gradiente quantistico determina il numero ottimale di cluster monitorando come la varianza intra-cluster cambia con l'aumento di K. Calcolare la varianza per i valori consecutivi di K e valutare il cambiamento tra di essi. Quando la riduzione della varianza scende sotto la soglia predefinita, i cluster aggiuntivi non migliorano più la compattezza e il corrispondente K viene selezionato come ottimale. Questo criterio basato sulla curvatura garantisce che il clustering si fermi nel punto in cui la struttura naturale nei dati viene catturata senza sovra-partizionamento.

Algoritmo 6: Ottimizzazione basata su gradiente quantistico

Input:
Un circuito quantistico parametrizzato QC(θ) con una porta di rotazione a un singolo qubit_{R Y}(θ).
Un osservabile quantistico = Z (valore di attesa di Pauli-Z).
Un intervallo di valori parametri θ.
Output: La seconda derivata f′′(θ) del valore atteso 〈Z〉 rispetto a θ.
Passaggi dell'algoritmo:
Passo 1: Inizializzare un circuito quantistico a qubit singolo QC(θ) con:
Una porta di rotazione parametrizzata R_Y(θ).
Misurazione sulla base computazionale (Z).
Passo 2: Definisci la funzione Evaluate_ Aspettativa(θ), cioè f′(θ) =
Assegnare il parametro θ al circuito.
Esegui il circuito su un simulatore quantistico con N colpi.
Misurare le probabilità di risultato P(0) e P(1).
Calcolare il valore atteso:
f(θ)=P(0)−P(1)
Passo 3: Calcola la seconda derivata usando la regola dello spostamento dei parametri:
Imposta il valore di spostamento s =
Calcolare i valori di attesa nei punti spostati:
f(θ+s), f(θ), f(θ−s)
Calcolare la seconda derivata:
f ′′(θ) =
Passo 4: f ′′(θ) per analizzare il comportamento di riduzione della varianza.

I dettagli di implementazione dell'approccio proposto al clustering quantistico sono forniti nella Tabella 2. La tabella specifica le funzioni eseguibili e le API utilizzate in ogni fase dell'algoritmo, inclusa la codifica delle caratteristiche nei circuiti quantistici, l'esecuzione del test SWAP per la stima della distanza, l'inizializzazione del centroide, la riassegnazione iterativa del cluster e la valutazione della varianza/ΔV. Sono inoltre elencati i parametri di esecuzione del circuito, come l'uso di SamplerV2 con il backend AerSimulator a 1024 colpi e l'ottimizzazione della traspilazione livello 1. Inoltre, la tabella illustra i metodi di visualizzazione applicati per generare diagrammi di scatter PCA, grafici di varianza e istogrammi, nonché le metriche di valutazione del clustering (silhouette_score, calinski_harabasz_score e davies_bouldin_score). Dettagliando specifiche funzioni a livello di comando e API, la tabella garantisce la riproducibilità di tutti i passaggi computazionali nell'algoritmo proposto.

Risultati

Un buon cluster dipenderà da vari fattori come la distanza di separazione tra i cluster, entro la distanza del cluster, il criterio del rapporto di varianza, ecc. Quindi, la performance di clustering è stata valutata utilizzando tre indici standard: il Silhouette Score, l'Indice Calinski-Harabasz (Indice CH) e l'Indice Davies-Bouldin (Indice DB). Il Silhouette Score misu...

Discussione

Questo studio propone un nuovo algoritmo ibrido di clustering quantistico K-Means con Detectione Ottimale di Cluster, progettato specificamente per classificare campioni tumorosi e non cancerosi utilizzando dati di espressione genica ad alta dimensione. L'approccio integra la mappatura quantistica multi-caratteristica, la stima quantistica delle distanze basata su Swap Test e l'ottimizzazione basata su gradiente quantistico per determinare dinamicamente il numero ottimal...

Materiali

Elenco dei materiali utilizzati in questo articolo

Nome	Azienda	Numero di catalogo	Commenti
Apple MacBook Pro (chip M1)	Apple Inc.	-	8 core CPU / 8 core GPU, 16? GB unified memory & mdash; Utilizzato per la simulazione locale
Dataset sull'espressione genica per il cancro al seno	Kaggle	-	Dataset con 569 campioni, 32 caratteristiche (ridotte tramite PCA nello studio)
macOS Monterey (Sistema operativo)	Apple Inc.	12.6.9	Ambiente di esecuzione utilizzato su macchine locali
matematica (libreria standard Python)	Python Software Foundation	Incorporato	Funzioni matematiche di base
Matplotlib	Comunità Matplotlib	3.8.4	Traccia e visualizzazione
NoiseModel, QuantumError, ReadoutError (Qiskit Aer)	Progetto IBM / Qiskit	parte di Aer 0.13.3	Utilizzato per simulare rumore quantistico realistico
NumPy	Sviluppatori NumPy	1.26.4	Operazioni numeriche e manipolazione degli array
Panda	Team di sviluppo Pandas	2.2.2	Gestione dei dati, I/O, operazioni tabellari
Python	Python Software Foundation	3.10.12	Linguaggio di programmazione, utilizzato nell'ambiente Jupyter / IPython
Qiskit Aer	Progetto IBM / Qiskit	0.13.3	Backend simulatore, con modellazione e esecuzione del rumore
Qiskit IBM Runtime – Session, SamplerV2	Progetto IBM / Qiskit	0.41.1	Framework di esecuzione per circuiti nel simulatore
Qiskit Terra	Progetto IBM / Qiskit	0.45.0	Quadro quantistico per la costruzione e traspilazione dei circuiti
scikit-learn	Sviluppatori scikit-learn	1.4.2	PCA, metriche di clustering, preprocessing dati