qalgora-Q Docs Hub量子文档 ✦ Ask AI✦ 问问文档
/

Divisive Clustering with Coresets

◐ Design-level API
This page documents qalgora-Q API design, architecture, or adaptation workflows. Code examples illustrate intended usage and are not guaranteed to run in the current reference implementation.

Cluster a large dataset on small quantum hardware by first compressing it to a weighted coreset, then recursively splitting it with QAOA Max-Cut.

Why coresets?

A coreset is a small weighted subset that approximates the full dataset. It shrinks an intractable problem down to a qubit count today's devices can handle.

The recursive split

One subtlety decides whether the split is even meaningful: what the edge weights mean. Max-Cut maximizes the total weight of edges crossing the partition, so if the weight were a similarity, the cut would tear apart the points that are most alike — exactly the wrong thing. The edge weight must therefore encode dissimilarity (or separation benefit), so that Max-Cut tends to place the most different points on opposite sides.

import qalgora

def divisive_cluster(points, weights, depth):
    if len(points) <= 1 or depth == 0:
        return [points]
    # encode a 2-way split as Max-Cut on a dissimilarity graph, solve with QAOA
    graph = weighted_dissimilarity_graph(points, weights)
    cut = qalgora_qaoa_maxcut(graph)
    left    = [p for p, b in zip(points, cut) if b == 0]
    right   = [p for p, b in zip(points, cut) if b == 1]
    left_w  = [w for w, b in zip(weights, cut) if b == 0]
    right_w = [w for w, b in zip(weights, cut) if b == 1]
    # carry the points AND their coreset weights into each branch
    return divisive_cluster(left,  left_w,  depth - 1) + \
           divisive_cluster(right, right_w, depth - 1)
Scaling
Coreset size sets the qubit count, decoupling problem size from hardware size — the same code scales from a simulator to a QPU by changing the target.
Approximation, end to end
Coreset compression is itself an approximation; the final clustering quality depends on the coreset construction, the weight definition, the graph edge-weight design, the balance constraints, and the quality of the QAOA solve.

基于核心集的分裂式聚类

◐ 设计接口
本页描述的是 qalgora-Q 的接口设计、架构设计或适配工作流。相关代码用于说明预期用法，当前参考实现不保证可以直接运行。

先将大型数据集压缩为加权核心集，再通过 QAOA Max-Cut 递归二分，从而在小规模量子硬件上完成聚类。

为何使用核心集

核心集是一个近似表示完整数据集的小型加权子集，能将规模难以处理的问题压缩至当前设备可支持的量子比特数量。

递归二分流程

有一处细节决定二分是否有意义：边权代表什么。Max-Cut 会最大化跨越划分的边权总和，因此若边权表示相似度，切割反而会把最相像的点撕开——恰恰是错的。这里的边权应表示不相似度或分离收益，使 Max-Cut 倾向于把差异大的点分到两侧。

import qalgora

def divisive_cluster(points, weights, depth):
    if len(points) <= 1 or depth == 0:
        return [points]
    # encode a 2-way split as Max-Cut on a dissimilarity graph, solve with QAOA
    graph = weighted_dissimilarity_graph(points, weights)
    cut = qalgora_qaoa_maxcut(graph)
    left    = [p for p, b in zip(points, cut) if b == 0]
    right   = [p for p, b in zip(points, cut) if b == 1]
    left_w  = [w for w, b in zip(weights, cut) if b == 0]
    right_w = [w for w, b in zip(weights, cut) if b == 1]
    # 同时把点与其核心集权重带入每个分支
    return divisive_cluster(left,  left_w,  depth - 1) + \
           divisive_cluster(right, right_w, depth - 1)
扩展性
核心集大小决定量子比特数量，从而将问题规模与硬件规模解耦——同一套代码只需切换目标即可从模拟器扩展至 QPU。
端到端的近似
核心集压缩本身是一种近似；最终聚类质量取决于核心集构造、权重定义、图边权设计、平衡约束以及 QAOA 求解质量。