Quantum Approximate Optimization Algorithm (QAOA) has been studied widely in the literature, primarily for finding an approximate value of the maximum cut size of a graph. QAOA is composed of a problem hamiltonian and a mixer hamiltonian which are applied alternately for p \geq 1 layers. The circuit for this algorithm requires 2m CNOT gatesin each layer, where m is the number of edges in the graph. CNOT gate is one of the primary sources of error in modern quantum computers. In this paper, we propose two techniques for reducing the number of CNOT gates in the circuit which are independent of the hardware architecture. For a graph with n vertices, we first propose a technique based on edge coloring that can reduce upto \lfloor n{2} \rfloor CNOT gates in the circuit . Next, we propose another technique based on Depth First Search (DFS) that can reduce n-1 CNOT gates at the cost of some increased depth . We analytically derive the criteria for which the reduction in the number of CNOT gates due to the DFS based technique can provide lower error probability even with some increased depth, and show that all graphs conform to this criteria, making this technique universal. We further show that this proposed optimization holds even in the post transpilation stage of the circuit , which is actually executed in the IBM Quantum hardware . We simulate these two techniques for graphs of various sparsity with the ibmq_manhattan noise model \textit{  and show that the DFS based technique outperforms the edge coloring based technique , which in turn, outperforms the traditional QAOA circuit in terms of reduction in the number of CNOT gates, and hence the probability of error of the circuit.
Quantum Approximate Optimization Algorithm (QAOA) is studied primarily to find approximate solutions to combinatorial optimization problems. For a graph with n vertices and m edges, a depth p QAOA for the Max-cut problem requires 2\cdot m \cdot p CNOT gates. CNOT is one of the primary sources of error in modern quantum computers. In this paper, we propose two hardware independent methods to reduce the number of CNOT gates in the circuit . First, we present a method based on Edge Coloring of the input graph that minimizes the the number of cycles (termed as depth of the circuit), and reduces upto \lfloor n{2} \rfloor CNOT gates . Next, we depict another method based on Depth First Search (DFS) on the input graph that reduces n-1 CNOT gates , but increases depth of the circuit moderately . We analytically derive the condition for which the reduction in CNOT gates overshadows this increase in depth, and the error probability of the circuit is still lowered. We show that all IBM Quantum Hardware satisfy this condition . We simulate these two methods for graphs of various sparsity with the \textit{ibmq\_manhattan noise model, and show that the DFS based method outperforms the edge coloring based method , which in turn, outperforms the traditional QAOA circuit in terms of reduction in the number of CNOT gates, and hence the probability of error of the circuit.
R
has been studied widely in the literature, primarily for finding an approximate value of the maximum cut size of a graph. QAOA is composed of a problem hamiltonian and a mixer hamiltonian which are applied alternately for p \geq 1 layers. The circuit for this algorithm requires 2m CNOT gatesin each layer, where m is the number of edges in the graph. CNOT gate
is studied primarily to find approximate solutions to combinatorial optimization problems. For a graph with n vertices and m edges, a depth p QAOA for the Max-cut problem requires 2\cdot m \cdot p CNOT gates. CNOT
R
techniques for reducing
hardware independent methods to reduce
R
which are independent of the hardware architecture. For a graph with n vertices, we first propose a technique based on edge coloring that can reduce
. First, we present a method based on Edge Coloring of the input graph that minimizes the the number of cycles (termed as depth of the circuit), and reduces
D
in the circuit
R
propose another technique
depict another method
R
that can reduce
on the input graph that reduces
R
at the cost of some increased depth
, but increases depth of the circuit moderately
R
criteria
condition
R
the number of CNOT gates due to the DFS based technique can provide lower error probability even with some increased
CNOT gates overshadows this increase in
R
show that all graphs conform to this criteria, making this technique universal. We further show that this proposed optimization holds even in the post transpilation stage
the error probability
R
, which is actually executed in the IBM Quantum hardware
is still lowered. We show that all IBM Quantum Hardware satisfy this condition
R
techniques
methods
D
ibmq_manhattan noise model
A
ibmq\_manhattan
A
noise model,
R
technique
method
R
technique
method