In noisy intermediate-scale quantum (NISQ) era, distributed quantum computing (DQC) has emerged as a promising direction to address limitations in qubit scalability and noise resilience. Entanglement forging is proposed as an important DQC protocol that enables the integration of the quantum computing resources and exhibits significant efficiency in realizing quantum states and dynamics with shallow entanglement. Here, we experimentally demonstrate the entanglement forging process for solving an eight-vertex Max-Cut problem. We execute parametrized quantum circuits on a four-qubit nuclear magnetic resonance quantum processor and successfully achieve the entanglement forging of the ground state for the eight-qubit Max-Cut Hamiltonian by using variational quantum eigensolver. The ground state reconstructed in experiment achieves a fidelity of 95.88% compared with theoretical prediction, which provides three correct solutions to the Max-Cut problem in parallel. Our work demonstrates the feasibility and efficiency of entanglement forging protocol in solving combinatorial optimization problems on NISQ devices, while also advancing the development of distributed quantum computing.
In noisy intermediate-scale quantum (NISQ) era, distributed quantum computing (DQC) has emerged as a promising direction to address limitations in qubit scalability and noise resilience. Entanglement forging is proposed as an important DQC protocol that enables the integration of the quantum computing resources and exhibits significant efficiency in realizing quantum states and dynamics with shallow entanglement. Here, we experimentally demonstrate the entanglement forging process for solving an eight-vertex Max-Cut problem. We execute parametrized quantum circuits on a four-qubit nuclear magnetic resonance quantum processor and successfully achieve the entanglement forging of the ground state for the eight-qubit Max-Cut Hamiltonian by using variational quantum eigensolver. The ground state reconstructed in experiment achieves a fidelity of 95.88% compared with theoretical prediction, which provides three correct solutions to the Max-Cut problem in parallel. Our work demonstrates the feasibility and efficiency of entanglement forging protocol in solving combinatorial optimization problems on NISQ devices, while also advancing the development of distributed quantum computing.
Variational quantum algorithms have promising applications in noisy intermediate-scale quantum (NISQ) devices. These algorithms rely on a classical optimization outer loop that minimizes a parameterized quantum circuit function. The optimization in variational quantum eigensolver (VQE) is NP-hard, meaning that finding the optimal solution is infeasible in the worst-case scenario. One way to address this challenge is through parallel optimization of parameters using multiple-parameterized quantum circuits. However, this approach is unsuitable for cloud-based quantum processing unit utilization due to the increased number of quantum circuit executions. Although NISQ devices have limitations in terms of gate depth, their size has been growing in recent years. Therefore, implementing multiple-parameterized quantum circuits in NISQ devices can suppress the increase in the number of executions. In this study, we propose a parallel-VQE, which leverages the parallel execution of parameterized quantum circuits to perform parallel parameter optimization in VQE, achieving convergence to solutions closer to the ground state. We validate the effectiveness of parallel-VQE in solving the random weighted max-cut problem using numerical simulations and a real quantum device. We present the results of running up to six circuits in parallel (120 qubits) and demonstrate the advantages of using multiple units to improve computational accuracy. This study provides a potential method for solving eigenvalue problems and combinatorial optimization problems for future quantum devices.
The max-cut problem (MCP) is a classic problem in the field of combinatorial optimization and has important applications in various fields, including statistical physics and image processing. However, except for some special cases, the MCP still encounters a non-deterministic polynomial complete problem (an NP-complete problem), and there is currently no known efficient classical algorithm that can solve it in polynomial time. The quantum approximate optimization algorithm (QAOA), as a pivotal algorithm in the noisy intermediate-scale quantum (NISQ) computing era, has shown significant potential for solving the MCP. However, due to the lack of quantum error correction, the reliability of computations in NISQ systems sharply declines as the circuit depth of the algorithm increases. Therefore, designing an efficient, shallow-depth, and low-complexity QAOA for the MCP is a critical challenge in demonstrating the advantages of quantum computing in the NISQ era.In this paper, according to the standard QAOA algorithm, we introduce Pauli Y rotation gates into the target Hamiltonian circuit for the MCP. By enhancing the flexibility of quantum trial functions and improving the efficiency of Hilbert space exploration within a single iteration, we significantly improve the performance of QAOA on the MCP.We conduct extensive numerical simulations using the MindSpore quantum platform, and compare the proposed RY-layer-assisted QAOA with standard QAOA and its existing variants, including MA-QAOA and QAOA+. The experiments are performed on various graph types, including complete graphs, 3-regular graphs, 4-regular graphs, and random graphs with edge probabilities between 0.3 and 0.5. Our results show that the RY-layer-assisted QAOA achieves higher approximation ratios in all graph types, particularly in regular and random graphs, where traditional QAOA variants are difficult to implement. Moreover, the proposed method exhibits strong robustness as the graph size increases, and can maintain high performance even for larger graphs. Importantly, the RY-layer-assisted QAOA requires fewer CNOT gates and has a lower circuit depth than the standard QAOA and its variants, making it more suitable for NISQ devices with limited coherence times and high error rates.In conclusion, the RY-layer-assisted QAOA provides a promising approach for solving MCP in the NISQ era. By improving the approximation ratio while reducing circuit complexity, this method demonstrates significant potential for practical quantum computing applications, thus paving the way for developing more efficient and reliable quantum optimization algorithms.
The current noisy intermediate-scale quantum (NISQ) era is characterized by substantial errors and noise, which limit the practical feasibility of deep, many-qubit circuits. To address these constraints, quantum circuit cutting has emerged as a promising tool. Recently, there has been significant research on methods for performing such cutting effectively. In this work, the duality between quantum circuits and classical graphs - specifically, directed acyclic graphs (dags) - is leveraged to analyze the complexity of finding an optimal circuit-cutting configuration that minimizes the number of cuts. After developing a rigorous graph-theoretic framework, the complexity of identifying cut locations that partition a given quantum circuit into smaller fragments is characterized. The corresponding graph-combinatorial task is then defined, and the resulting partition problem is shown to be NP-complete. Furthermore, even a simplified version of the problem, restricted to circuits composed only of one- and two-qubit gates, is shown to be NP-complete. Finally, based on these constraints, an algorithm grounded in satisfiability modulo theories (SMT) is proposed to find optimal cuts when the number of qubits per partition is bounded. This work therefore provides a complexity-theoretic characterization of cut placement and a practical solver for bounded-size decompositions.
The Ising machine, as a quantum-inspired computing system, can be used to efficiently solve combinatorial optimization problems. Ongoing studies have positioned it to potentially surpass the performance limitations of traditional computers. However, such Ising machines also suffer from scalability as the solution quality becomes sub-optimal when the problem size increases. In this work, we propose an Ising-based framework that uses a distributed Ising algorithm to find the near-optimal solution for large-scale Max-Cut problems through parallel processing via graph segmentation and reassembly. We selected the coherent Ising machine as the hardware solver and successfully found the solution for a 2000-node instance utilizing 20 computational bits on the Gset standard dataset. Additionally, we investigated the key factors influencing the system's performance and discovered that setting the number of reorganizations to one results in higher accuracy. Building on this configuration, we utilized a 100-bit CIM hardware platform (CPQC-1) to solve instances with varying numbers of nodes. The experimental results agree well with the theoretical simulations, confirming the practical feasibility of our method. Moreover, compared to existing Ising-based solvers, our algorithm significantly reduces computational resource requirements while achieving superior performance on large-scale combinatorial optimization problems, highlighting its effectiveness on quantum-inspired hardware.
Distributed Quantum Computing (DQC) offers a promising path toward scalable quantum computation by connecting multiple quantum processors through quantum and classical communication channels, helping overcome the limited qubit counts and noise of individual Noisy Intermediate-Scale Quantum (NISQ) devices. Beyond scaling, DQC has been shown to provide a provable computational advantage: Balliu et al. (STOC 2025) proved that certain locally checkable labeling problems require Ω(Δ) rounds classically in the LOCAL model, where Δ is the maximum degree of the graph, yet only a single round in the quantum-LOCAL model. This separation is unconditional, but a practical demonstration on real hardware had not previously been carried out. This thesis addresses that gap through two contributions. First, it covers the background needed to understand distributed quantum computing: quantum gates, entanglement and the GHZ state, classical distributed models such as LOCAL and CONGEST, locally checkable labeling problems, and the operating principles of superconducting quantum computers, including the practical challenges of connecting them across distances. Second, it presents a practical demonstration of the iterated GHZ game, the locally checkable labeling problem underlying the separation above. The quantum-LOCAL winning strategy is proven correct and implemented as a quantum circuit, executed on IQM’s superconducting quantum computers Garnet and Emerald via the IQM Resonance cloud service. Since physically distributed superconducting hardware is not yet publicly available, a chip-partitioning scheme is used, treating regions of a single chip as independent quantum nodes to emulate a distributed network. The results show that Round 1 games consistently exceed the 75% classical winning bound of the GHZ game, confirming that this win-rate quantum advantage is detectable under NISQ-era noise. In a deeper 3-round demonstration, performance degrades in later rounds, suggesting that demonstrating the advantage consistently across deeper circuits will require longer coherence times, higher gate fidelities, or error correction.
Quantum computers in the noisy intermediate-scale quantum (NISQ) era are constrained by limited qubit counts, imperfect gate fidelities, and short coherence times. NISQ-era computers often have too few qubits to run many algorithms, and those that do run often have limited quantum advantage. Distributed quantum computing (DQC) is a promising approach to overcome this, where multiple quantum processors are interconnected through shared entanglement. This work serves as a system overview of an entanglement distribution system. We achieve this by examining a zero-added loss multiplexing (ZALM) entanglement generation source, simulating multi-hop, repeater-less networks, and various routing algorithms to distribute entanglement, and real-hardware quantum experiments that reconstruct entanglement links of degraded fidelity and simulate classical-communication delay. Network simulations evaluate routing and spectrum-allocation algorithms under entanglement-generation-imposed rate constraints, by evaluating both fairness and throughput across network sizes and topologies. We identify two polynomial-time approximation algorithms that perform well, or better than others under these metrics. Using both simulations and quantum hardware, we evaluate how degraded entanglement and communication latency affect teleportation-based distributed multipartite-entanglement-state construction. The results reveal the coupled influence of source rate, routing efficiency, fidelity, and classical delay on networked entanglement distribution and DQC performance, providing a reproducible framework for both experimental and simulated studies of near-term DQC.