Error correction progress: Scientists improve quantum state fidelity by an average of 23%
Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising hybrid quantum-classical algorithms, which can be used to solve difficult problems such as combinatorial optimization problems and maximum partitioning problems. However, the high error rate and limited fidelity of quantum gates in near-term quantum devices are major obstacles to the successful implementation of QAOA algorithms.
Recently, under the auspices of Oak Ridge National Laboratory's Quantum Computing User Program (QCUP), Ruslan Shaydulin of Argonne National Laboratory Research Institute and Alexey Galda, research assistant professor at the University of Chicago and chief scientist at Menten AI, a quantum algorithm company, collaborated to exploit the classical objective function The presence of symmetry in QAOA reduces errors in the evolution of QAOA. Specifically, the QAOA states are projected into a symmetry-constrained subspace, and the projection is performed at the end of the circuit or throughout the evolution. They verified the method using five qubits in an IBM quantum processor. When exploiting global bit-flip symmetry, quantum state fidelity was improved by an average of 23 percent—one of the most successful improvements to quantum problems to date. The paper has been published at the 2021 IEEE International Conference on Quantum Computing and Engineering [1].
Quantum Approximate Optimization Algorithms
The Quantum Approximate Optimization Algorithm (QAOA) is a quantum-classical hybrid algorithm that can approximately solve combinatorial optimization problems on quantum computers. The goal of QAOA is to prepare a quantum state and obtain, with high probability, a binary string that maximizes the value of the objective function when measured. However, one of the main obstacles to its successful implementation is the lack of fully error-correcting equipment. The limitation of noise on QAOA performance is as follows: with the increase of circuit depth, QAOA performance begins to decline.
As shown in Figure 1, the noise and infidelity of quantum gates impose an effective upper limit on the number of executable QAOA steps.
Therefore, increasing the QAOA alternation operators that can be performed before reaching the noise limit is crucial for the successful application of QAOA. This can be achieved by reducing the error rate in hardware or by mitigating errors through software and algorithmic techniques.
Figure 1 In the MaxCut problem, the expected maximum cut value <C> for a binary string sampled from the QAOA state for a star graph with 4 nodes. Green represents the noise-free simulation, and the yellow and gold lines represent the results for qubits 1-4 of ibmq_bogota.
Classical symmetry of the objective function
By verifying the classical symmetry of the objective function, the errors that occur during the execution of QAOA evolution on noisy quantum computers are mitigated. In this paper, two classes of objective function symmetries are considered: bit-flip symmetry and variable (qubit) exponential permutation symmetry.
Figure 2 Circuit used to verify the symmetry of the objective function. To reduce errors, the measurement results are post-selected when the auxiliary qubit is equal to 0. This process can be applied at the end of a circuit or inserted between alternating operators throughout the evolution.
The first type of symmetries are bit-flip symmetries. The symmetric form is a(x)=x⊕l, where l is a binary string. The circuit is shown in Figure 2A, where CNOT is applied on a subset F of qubits. The second type of symmetry is the variable (qubit) exponential permutation symmetry, ie the symmetry a∈Sn. For simplicity, this paper only considers a subset of permutation symmetries, which can be represented by a series of non-overlapping quantum exchange gates (SWAP). Therefore, the symmetry verification circuit can be constructed according to the method shown in figure 2B.
QAOA applied to the Maxcut problem
Consider an undirected graph G with a set of vertices V and a set of edges E. The goal of the max-cut problem is to assign vertices to two disjoint subsets such that the number of edges spanning the two subsets is maximized. Generally speaking, the maximum cut target is encoded by the Hamiltonian:
For QAOA applied to the max-cut problem, the researchers verified two types of symmetries: the first is the global bit-flip symmetry exhibited by all max-cut instances; the second is the variable (qubit) exponential permutation symmetry .
The researchers performed experiments on a 7-qubit ibmq_jakarta superconducting processor, utilizing up to 5 qubits, and made public all quantum circuits used in the experiments [2]. Specifically, they considered the following four graphs with symmetry: 3-node path graph (pmax=1), 3-node complete graph (pmax=2), 4-node star graph (pmax=3), and 4-node graph Kite plot (pmax=3). In all experiments, the researchers mapped the QAOA circuit onto qubits 0, 1, 3, and 5 of ibmq_jakarta, as shown in Figure 3.
Figure 3 Graph and ibmq_jakarta layout of the maximum cut instance. The qubits used in the experiments are highlighted in red.
Reduce errors in 7-qubit superconducting device
To calculate the fidelity of quantum states, the researchers performed quantum state tomography: inferring quantum states from measured statistics using maximum likelihood estimation.
Figure 4 shows the results obtained by applying symmetry verification to the maximum-cut QAOA circuit on ibmq_jakarta. The figure shows: the fidelity of the quantum state, the expected value of the objective <C>, and the probability Pr(x∗) of sampling the binary string that maximizes the objective function. Error bars for <C> values show the sample mean plus or minus one standard deviation. They observed that the fidelity of the global bit-flip symmetry verification all improved (leftmost column of Figure 3). The improvement in fidelity comes from the fact that the values of <C> and Pr(p∗) grow with the depth p of the noiseless state, offsetting the drop in fidelity between the noiseless state and the state on hardware.
Figure 4 Symmetry Verification (SV) of QAOA for max-cut on ibmq_jakarta. MeasEM represents results with measurement error mitigation, which is done by computing and inverting the calibration matrix using an open source implementation in Qiskit. Error bars for <C> values show the sample mean plus or minus one standard deviation. The results show that the fidelity of symmetry verification improves over the baseline (without SV) in all instances with bit-flip symmetry.
However, the researchers did not observe an improvement in fidelity with variable (qubit) exponential permutation symmetry verification on ibmq_jakarta. They hypothesize that this effect is local due to the higher relative overhead and the considered permutation symmetry. To emphasize the promise of this approach with fewer sources of error on the hardware. They supplemented the results obtained on ibmq_jakarta with noise simulations.
Figure 5 shows the noisy simulation results. Noise simulations are performed using the Aer module of the Qiskit software framework, and the simulated objects are derived using calibrated gate error rates and coherence times on a quantum processor, and a noisy quantum circuit simulator is provided. At the same time, the noisy model also takes into account the depolarization error of the two-qubit gate - the latest device calibration information provided by IBM Quantum.
Figure 5 Symmetry verification (SV) results from depolarization noise channel and thermal relaxation simulations. The error model is calibrated using parameters obtained from the ibmq_jakarta calibration data.
It can be observed that the increase in fidelity comes with a decrease in the relative overhead of symmetry verification. Unlike bit-flip symmetry, for qubit permutation symmetry, the results do not show an improvement for all depths p. In fact in the simulations it is only observed that the fidelity of the simulation improves only in the case of p=3. This supports the intuition that permutation symmetry verification is too expensive to be ineffective for relatively shallow circuits due to high hardware error rates. Because for larger instances, greater depth is required, the relative overhead of symmetry verification will be lower, making it more advantageous in hardware.
A major innovation in improving the fidelity of quantum states
QAOA is a promising approach to using quantum computers to accelerate combinatorial optimization problems, but it requires relatively deep circuits to succeed: QAOA depth must grow at least logarithmically with the size of the problem to achieve quantum advantage. At the same time, implementing QAOA on a fixed-qubit architecture, such as the superconducting processor used in this work, requires routing qubits through a network of quantum SWAP gates, which generally incur a linear cost if two-qubit gates are used.
Combining the above two observations, if no error correction is performed with a constant error rate, the fidelity of the quantum state, the probability of success, decays exponentially with the number of operations.
Therefore, developing effective error mitigation techniques is a prerequisite for QAOA to achieve quantum advantage. This paper helps bridge the gap between today's NISQ devices and future fault-tolerant quantum computers, enabling significant improvements in quantum fidelity.
Reference link:
[1] https://ieeexplore.ieee.org/document/9605320/authors#authors
[2]https://github.com/rsln-s/Error-Mitigation-for-Deep-Quantum-Optimization-Circuits-by-Leveraging-Problem-Symmetries
