Based on optical quantum circuits, Pan's team has made another important breakthrough!

Solving the independent set (IS) problem or other combinatorial optimization problems has a wide range of applications in fields as diverse as economics, biology, chip design, and computer vision.

For typical structures such as line graphs, planar graphs, and tree graphs, finding all their independent sets is a polynomially complex problem that can be solved by classical algorithms; however, for general graphs, finding all their maximal IS has been shown to be an NP-complete (NP-complete) problem.

Nevertheless, heuristic algorithms can be used to find an approximate maximum IS. at this point, adiabatic quantum computing offers a natural way to solve the IS equivalence problem, and has attracted strong interest due to its potential speedup over classical algorithms. In adiabatic quantum computing, a quantum system is first prepared in a simple initial ℋ0 ground state and then slowly transformed into a complex target Hamiltonian ℋtarget. the quantum adiabatic theorem guarantees that if the Hamiltonian changes slowly enough, the system will eventually reach the ℋ target's ground state.

However, the minimum energy gap Δmin between the ground and first excited states of the time-dependent many-body Hamiltonian generally decreases exponentially with the size of the system, which means that the running time T required for the adiabatic process increases exponentially. Therefore, although the basic concept of adiabatic evolution between ℋ0 and ℋtarget is simple and general, choosing a suitable initial Hamiltonian ℋ0 and an easily implemented evolution path to solve a specific combinatorial optimization problem can be a physically challenging task.

Fortunately, for IS-equivalent problems, the corresponding many-body system possesses considerable non-abelian canonical symmetry - a property that we can exploit. It allows us to choose ℋIS as the initial and target Hamiltonian. By driving the system to evolve slowly along a closed path, an easily prepared initial ground state will be transformed into a superposition of computational basis states (i.e., the corresponding independent sets) containing ℋIS to obtain a solution to the IS problem. This process can be regarded as the "quantum diffusion" in the median diagram, which is named non-Abelian adiabatic mixing (NAAM).

The article was published in PNAS under the title "Solving independent set problems with photonic quantum circuits".

In the article published in the Proceedings of the National Academy of Sciences (PNAS) on May 22, a joint team of Pan, Yu-Ao Chen, Frank Wilczek, and Xing-Can Yao reported a proof-of-principle of NAAM using an advanced linear optical quantum network (LOQN) to solve the IS problem on the general graph G(8, 7).

Since G(8, 7) has seven edges, at least seven probabilistic two-bit C-Phase gates are required to approximate the NAAM, resulting in an extremely low probability of success for the LOQN (on the order of ∼10-7). To overcome this obstacle, the team developed a method to implement deterministic double quantum bit gate arrays (DGAs) by combining path-polarized hyperentanglement. By placing four DGAs at the end layer of the LOQN, the overall success probability is increased by four orders of magnitude.

From the figure to the conceptual circuit. (A) Representative graph G(8, 7) without breakpoints. (B) Illustration of the "quantum diffusion" process in an 8-dimensional diagram. The black and blue dots represent the real states, i.e., the computational ground states of H|gn⟩, while the red and hollow dots represent the false states, i.e., the computational ground states that do not belong to|gn⟩. The solid and dashed lines between the two points represent the allowed and forbidden paths in the "quantum diffusion" process, respectively. Finally, the black and blue dots connected by the solid line in the figure form the median diagram of the IS problem G(8, 7). (C) Schematic diagram of the circuit implementing Wilczek-Zee holonomy ΓG(8, 7) with Trotterization step m. Each building block corresponds to an 8-qubit fully connected linear optical quantum network. The purple layer represents the Hamiltonian quantity ℋ13 + ℋ57; the light blue layer corresponds to ℋ37; the dark blue layer is used to implement ℋ12 + ℋ34 + ℋ56 + ℋ78.

Deterministic gate array (DGA) for the implementation of the concept circuit. (A) Quantum circuit of the DGA. The upper (lower) quantum bits are the polarization (spatial) modes of a single photon; Ub and Ur represent SU(2) rotating gates implemented by an HWP sandwiched between two QWPs. (B) Experimental setup. The input PBS and output PBS combined with the Ub and Ur gates on the blue and red paths are used to construct the DGA, which converts the input polarization state to a polarization-space entangled state. The Sagnac interferometer ensures the phase stability between the two arms. (C) The real and imaginary parts of the experimental process matrix χex. The implementation of the high-fidelity DGA greatly improves the probability of success of our shallow circuit and paves the way for a high-precision solution of the IS problem G(8, 7).

Physical implementation of the experiment. Two pulsed ultraviolet (UV) lasers (390-nm wavelength, 140-fs pulse duration, 76-MHz repetition rate, 300-mW pump power) were used to generate two correlated photon pairs 1\AMP 2 and 3\AMP 4 simultaneously through two BBO crystals via a beamlike type-ii@ SPDC process.Then, these four photons were injected into a shallow circuit that consists of ten single-bit rotary gates, three C-Phase gates, and four DGAs. Eight detection modules are placed in the output ports of the shallow circuit. Finally, photons are detected by 16 fiber-coupled single-photon detectors (quantum efficiency >60%) and all 256 octet coincidence events are registered by an FPGA-based coincidence counting system.

The DGA has six independently tunable parameters, corresponding to one C-Unitary gate sandwiching two C-NOT gates, resulting in a much deeper quantum circuit that yields a high process fidelity of 0.930. In addition, all solutions including the five largest independent sets (01011001), (01101001), (10010101), (10010110), and (10011001) were successfully determined by measuring the final superposition state on the σz basis.

Experimental results

The team said, "Our work opens up the prospect of solving more complex IS equivalence problems by performing NAAM on future large-scale programmable LOQNs."

This experiment implements a non-Abelian adiabatic mixing process, solving the general IS problem G(8, 7) based on advanced LOQNs. Due to the high flexibility and complexity of LOQNs, the team achieved a fairly high fidelity of the non-abelian adiabatic mixing process - 0.930. This in turn successfully solved the IS problem: e.g., obtaining the maximum independent set, a high success probability of finding a solution of 0.875, and a respectable probability of finding a nonlinear solution of 31.4%.

Also, the paper mentions that "our current experiments have two main limitations: i) the small probability of finding the maximum independent set and ii) the scalability problem of solving the larger IS problem G(V, E). Nevertheless, our work shows that NAAM can be used as an efficient and general approach to solve IS-equivalent combinatorial optimization problems with intrinsic non-abelian regular symmetries."

In the future, the exploration of potential quantum acceleration of NAAM-based algorithms with advancing large-scale quantum simulators could lead to near-term practical applications, such as quantum optimization of MIS problems in Riedberg atomic arrays, quantum approximate optimization of graph problems in superconducting processors, and quantum simulation of non-abelian gauge theories with qudit systems.

Link to original article:

https://www.pnas.org/doi/10.1073/pnas.2212323120