Quantum Computing Research CenterBuilding Efficient Algorithms with Error Correction, Clustering, and Noise Mitigation

The concept of quantum computing began to take shape in the 1980s, and a major breakthrough came in 1994 with the introduction of Shor's algorithm, which drew worldwide attention from the scientific community. Today, quantum computers with hundreds of qubits have already been built.

However, qubits are extremely susceptible to environmental noise. As their number increases, error rates grow exponentially. To ensure computational accuracy, quantum error correction (QEC) is essential for detecting and correcting these errors.

The Golden Triangle of Quantum Error Correction

Error rates in today's quantum computers remain high. Even with a fidelity of 99.9999%, about one error per million operations, a practical quantum algorithm may require up to 109 computations. Without error correction, a single error could invalidate the entire computation.

For this reason, quantum error correction (QEC) has been a central focus of the Quantum Computing Research Center (QCRC) since its founding. At its core, QEC relies on redundancy.

For example, in classical systems, a bit “1” can be transmitted three times as “111.” Even if one bit flips to “101” in error, the receiver can still correctly identify the original bit as “1” by majority voting.

In quantum systems, however, error correction is far more complex. It involves balancing three critical parameters: N, the number of encoded qubits; K, the number of logical (original) qubits; and D, the number of correctable errors. As the number of correctable errors increases (i.e., a larger D), the required redundancy (N–K) also grows, which in turn reduces the amount of usable data (K) that can be transmitted. The QCRC is dedicated to finding optimal trade-offs among these three parameters.

International Collaboration for Optimal Parameters

In addition to minimizing errors, measurement efficiency is also critical. Ideally, error-correcting codes should be low-density, meaning that only a small subset of qubits needs to be measured to identify and fix errors, rather than examining all qubits. This ensures both efficiency and precision.

Another key design consideration is geometric locality; the qubits to be measured should be physically close to each other rather than widely dispersed. This helps shorten the actual distance between qubits, minimizing latency and reducing the complexity of quantum hardware design.

In other words, the challenge of QEC lies in encoding and decoding: how to detect and correct errors rapidly and accurately while using as few qubits as possible. This problem has remained unresolved for decades.

In 2023, QCRC collaborated with Caltech (USA) and the Weizmann Institute of Science (Israel) to propose an optimal construction method for quantum low-density parity-check (qLDPC) codes and develop a high-efficiency linear-time decoder whose runtime scales with qubit count. This breakthrough enables data protection with minimal redundancy while achieving optimal error-correction performance, resolving a challenge that had persisted for over two decades.

Building on this, in 2024 the team further integrated geometric locality into their error-correcting codes. These new designs not only minimize the number of measurement points needed to identify errors but also physically cluster those points, significantly reducing the complexity of quantum hardware design.

The results, which combine optimal parameters with geometric locality, were presented at QIP 2024, one of the world's leading quantum computing conferences. “This is not only a technical breakthrough,” noted QCRC Director Min-Hsiu Hsieh,“ it also demonstrates that our team is now among the global leaders in quantum error correction.”

From Social Networks to Logistics: Delivering Quantum Solutions

In addition to breakthroughs in QEC, QCRC also collaborated with Université Paris to develop a quantum graph clustering algorithm. This approach offers more efficient solutions to problems that can be abstracted into graph structures, as well as clustering and classification tasks.

For instance, quantum graph clustering can analyze nodes within a network to map complex social connections, such as distinguishing individuals with the same name across different communities and analyzing complex interpersonal relationships. The team demonstrated a clear quantum advantage. Compared to the classical algorithm's computational complexity of O($\sqrt{N}$), the graph clustering algorithm developed by QCRC achieves a complexity of O($3\sqrt{N}$).

This means that as problem sizes increase, the graph clustering algorithm developed by QCRC requires computational resources that increase more slowly, allowing quantum computers to tackle larger problem sizes than classical systems under the same resource constraints.

In addition, the study was the first to establish a theoretical lower bound for such problems, precisely defining the performance limits of classical algorithms. This is a critical milestone in computer science, as it enables researchers to assess the efficiency of corresponding quantum algorithms with theoretical certainty. With this, the team can confidently apply high-efficiency quantum algorithms to real-world problems without wasting resources on inefficient methods.

More importantly, applications of quantum graph clustering algorithms are not limited to social media. Its true potential lies in recasting complex real-world problems into graph clustering problems that can be solved more efficiently with quantum algorithms. Examples include matching drivers and passengers in ride-sharing services, optimizing logistics, streamlining production line workflows, and improving industrial manufacturing efficiency.

Noise Mitigation to Enhance Computational Accuracy

Another major 2024 achievement from QCRC is the breakthrough in quantum state tomography.

While quantum computers are powerful, they are also highly susceptible to noise. To realize their computational advantage, noise must be reduced below a certain threshold, making signal denoising in quantum states particularly important. A quantum state refers to the configuration of a quantum system. Its preparation is complex and requires computation to verify correctness. However, quantum states cannot be directly observed; only partial measurement results can be obtained under specific conditions.

Certain quantum states are essential for realizing quantum advantage. Without them, some quantum operations are no better than classical computation. Efficiently generating and accurately verifying these quantum states is therefore a central challenge.

Quantum state tomography addresses this issue by reconstructing qubit states through a series of precise measurements, ensuring the accuracy of hardware operations. A key technique is the Riemannian gradient descent, which significantly reduces the time required for quantum state reconstruction.

Breaking the Bottleneck in Quantum State Reconstruction

Quantum state is typically represented by matrices, whose size grows exponentially with the number of qubits. As a result, the amount of data required for quantum state tomography increases drastically. This makes data collection and full state reconstruction prohibitively demanding and time-consuming.

Fortunately, quantum states are not entirely random; they follow intrinsic structures. By exploiting these patterns with the Riemannian gradient descent, the QCRC team greatly improved quantum state reconstruction efficiency. Their results were published in Physical Review Letters, highlighting the international significance and academic rigor of their work.

Looking ahead, Director Hsieh envisions QCRC continuing to advance along three key areas: hardware enablement, software algorithms, and real-world applications.Together, these efforts aim to accelerate the commercialization of quantum computing.