Approximating the quantum approximate optimization algorithm with digital-analog interactions

The quantum approximate optimization algorithm was proposed as a heuristic method for solving combinatorial optimization problems on near-term quantum computers and may be among the first algorithms to perform useful computations in the postsupremacy, noisy, intermediate-scale era of quantum computing. In this work we exploit the recently proposed digital-analog quantum computation paradigm, in which the versatility of programmable universal quantum computers and the error resilience of quantum simulators are combined to improve platforms for quantum computation. We show that the digital-analog paradigm is suited to the quantum approximate optimization algorithm due to the algorithm's variational resilience against the coherent errors introduced by the scheme. By performing large-scale simulations and providing analytical bounds for its performance in devices with finite single-qubit operation time we observe regimes of single-qubit operation speed in which the considered variational algorithm provides a significant improvement over nonvariational counterparts in the digital-analog scheme.

Figure 1

The two schemes for digital-analog computation. (a) The stepwise or sDAQC scheme in which a series of programmable digital single-qubit gates are applied in alternation with analog resource interactions. (b) The always-on or bDAQC scheme in which the resource interaction is never turned off and single-qubit operations are applied in parallel with the resource interactions. Performing the single-qubit operations simultaneously with the resource interaction introduces coherent errors but reduces device control requirements. The first interaction block denoted with the time interval $t_0$ corresponds to the idle block.

Figure 2

A quantum circuit depicting the digital-analog time evolution required to simulate an arbitrary Ising Hamiltonian on five qubits. Ten uses of a resource Hamiltonian are required, each surrounded by a unique combination of single-qubit $X$ operations.

Figure 3

A typical QAOA state preparation circuit. A problem and driver Hamiltonian are alternated $p$ times, applied to the ${|+\rangle }^n$ state, followed by measurement on all qubits.

Figure 4

The process followed in QAOA. A loop of calculating expectation values and changing parameters is run until a satisfactory string is found.

Figure 5

Circuit showing the decomposition of a SAT-clause problem Hamiltonian using only $Z$-type operators. $a$ describes the type of the SAT clause, with $a=0$ being an OR clause between un-negated variables.

Figure 6

Circuit compilations for an eight-qubit MAX-CUT problem on a five-regular graph. (a) A decomposition of the MAX-CUT problem Hamiltonian into $ZZ$ interactions. The lines connected to two open circles represent $ZZ$ interactions applied for time $t_{\mathrm{int}}$. On the right-hand side, we see that the circuit can be parallelized into six time steps, each of which sees one qubit interact with only one other qubit at a time. Six time steps corresponds to the maximum degree of a vertex plus one. (b) The same circuit can be compiled into the scheme of sDAQC in which a resource all-to-all homogeneous Ising Hamiltonian is turned on and off, punctuated by single-qubit gates. This decomposition requires 20 uses of the resource Hamiltonian and 50 single-qubit $X$ operations. The time taken to apply the problem Hamiltonian is $5t_{\mathrm{int}}+21t_X$. (c) Finally, we compile the problem Hamiltonian in the bDAQC scheme, in which the resource Hamiltonian remains on throughout the procedure. This circuit only approximates the time evolution invoked by the QAOA problem Hamiltonian but can be carried out in time $5t_{\mathrm{int}}$ and also with 49 single-qubit $X$ operations. In the limit of infinitely fast $X$ gates, (c) is equivalent to (a) and (b).

Figure 7

Plots showing the on-device required time for implementation of a QAOA problem Hamiltonian. In this case random Erdős Rényi MAX-CUT problems are used with a filling factor of 0.75. Units of time are defined relative to the native device resource interaction strength. In these plots we show the time taken when using various possible resource Hamiltonians. The left-hand side demonstrates that if the resource Hamiltonian available varies across orders of magnitude in coupling strength, as happens in the case of an inverse power-law coupling between qubits in an array, the time taken in the digital-analog scheme becomes extremely large (and likely impractical). The right plot shows the series in the left excluding the inverse power-law couplings. A homogeneous resource Hamiltonian is competitive with an idealized digital compiling scheme, though higher for qubit numbers higher than 10. The upper blue (square marker) and green (circle marker) lines demonstrate that if we use a resource Hamiltonian with normally distributed couplings close to 1 (standard deviations 0.05 and 0.1), the time taken is longer. The significant gap between the homogeneous and nonhomogeneous series occurs as the periodicity of the homogeneous resource Hamiltonian's effected time evolution can be exploited to reduce the idle time. The units for time displayed in the plot are dimensionless multiples of a timescale defined by the resource Hamiltonian.

Figure 8

The percentage difference between the mean approximation ratio attained by bDA-QAOA and error-free QAOA, averaged over 50 randomly generated MAX-CUT problems with constant filling factor $p_{\mathrm{clause}}=0.7$. Blue (dark region on the far left side of the figure) colors indicate that the bDA-QAOA Ansatz state is worse than that provided by error-free QAOA, whereas shades of brown (the light gray region immediately left of the white region of zero error) indicate an improvement of the bDAQC over error-free QAOA. On the $x$ axis, the ratio $\alpha$ of single-qubit to problem Hamiltonian term strength is seen where error-free QAOA exists in the limit as this ratio becomes infinite.

Figure 9

The percentage difference in mean approximation ratio attained by bDA-QAOA at parameters maximizing error-free QAOA and bDA-QAOA with optimized parameters, averaged over 50 randomly generated MAX-CUT problems with constant filling factor $p_{\mathrm{clause}}=0.7$. On the $x$ axis, the ratio $\alpha$ of single-qubit to problem Hamiltonian term strength is seen where error-free QAOA exists in the limit as this ratio becomes infinite. Darker colors imply that for the concerned speed ratio and qubit number, the variational nature of QAOA can account for differences between bDA-QAOA and the ideal algorithm. This plot shows the benefit of using a variational algorithm such as QAOA over a nonvariational algorithm in the DA context where coherent error is introduced.