We introduce a quantum divide and conquer algorithm that enables the use of distributed computing for constrained combinatorial optimization problems. The algorithm consists of three major components: classical partitioning of a target graph into mul
tiple subgraphs, variational optimization over these subgraphs, and a quantum circuit cutting procedure that allows the optimization to take place independently on separate quantum processors. We simulate the execution of the quantum divide and conquer algorithm to find approximate solutions to instances of the Maximum Independent Set problem which have nearly twice as many nodes than the number of qubits available on a single quantum processor.
We present a new hybrid, local search algorithm for quantum approximate optimization of constrained combinatorial optimization problems. We focus on the Maximum Independent Set problem and demonstrate the ability of quantum local search to solve larg
e problem instances on quantum devices with few qubits. The quantum local search algorithm iteratively finds independent sets over carefully constructed neighborhoods and combines these solutions to obtain a global solution. We compare the performance of this algorithm on 3-regular graphs with up to 100 nodes against the well known classical Boppana-Halld{o}rsson algorithm for the Maximum Independent Set problem.
We study the costs and benefits of different quantum approaches to finding approximate solutions of constrained combinatorial optimization problems with a focus on Maximum Independent Set. In the Lagrange multiplier approach we analyze the dependence
of the output on graph density and circuit depth. The Quantum Alternating Ansatz Approach is then analyzed and we examine the dependence on different choices of initial states. The Quantum Alternating Ansatz Approach, although powerful, is expensive in terms of quantum resources. A new algorithm based on a Dynamic Quantum Variational Ansatz (DQVA) is proposed that dynamically changes to ensure the maximum utilization of a fixed allocation of quantum resources. Our analysis and the new proposed algorithm can also be generalized to other related constrained combinatorial optimization problems.
We introduce maximum likelihood fragment tomography (MLFT) as an improved circuit cutting technique for running clustered quantum circuits on quantum devices with a limited number of qubits. In addition to minimizing the classical computing overhead
of circuit cutting methods, MLFT finds the most likely probability distribution for the output of a quantum circuit, given the measurement data obtained from the circuits fragments. We demonstrate the benefits of MLFT for accurately estimating the output of a fragmented quantum circuit with numerical experiments on random unitary circuits. Finally, we show that circuit cutting can estimate the output of a clustered circuit with higher fidelity than full circuit execution, thereby motivating the use of circuit cutting as a standard tool for running clustered circuits on quantum hardware.
The maximum independent set (MIS) problem of graph theory using the quantum alternating operator ansatz is studied. We perform simulations on the Rigetti Forest simulator for the square ring, $K_{2,3}$, and $K_{3,3}$ graphs and analyze the dependence
of the algorithm on the depth of the circuit and initial states. The probability distribution of observation of the feasible states representing maximum independent sets is observed to be asymmetric for the MIS problem, which is unlike the Max-Cut problem where the probability distribution of feasible states is symmetric. For asymmetric graphs it is shown that the algorithm clearly favors the independent set with the larger number of elements even for finite circuit depth. We also compare the approximation ratios for the algorithm when we choose different initial states for the square ring graph and show that it is dependent on the choice of the initial state.
We study the results of a compiled version of Shors factoring algorithm on the ibmqx5 superconducting chip, for the particular case of $N=15$, $21$ and $35$. The semi-classical quantum Fourier transform is used to implement the algorithm with only a
small number of physical qubits and the circuits are designed to reduce the number of gates to the minimum. We use the square of the statistical overlap to give a quantitative measure of the similarity between the experimentally obtained distribution of phases and the predicted theoretical distribution one for different values of the period. This allows us to assign a period to the experimental data without the use of the continued fraction algorithm. A quantitative estimate of the error in our assignment of the period is then given by the overlap coefficient.
We present a simple model which allows us to explain the physical nature of the oscillating entropy. We consider an ensemble of qubits interacting with thermal two-level systems. The entropy of the qubits oscillates between zero and the value of entr
opy of the thermal systems. We show that the oscillations of the entropy can be clearly explained by the precession of the real or effective spins of the qubits.
