Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
64
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The Quantum Approximate Optimization Algorithm can naturally be applied to combinatorial search problems on graphs. The quantum circuit has p applications of a unitary operator that respects the locality of the graph. On a graph with bounded degree, with p small enough, measurements of distant qubits in the state output by the QAOA give uncorrelated results. We focus on finding big independent sets in random graphs with dn/2 edges keeping d fixed and n large. Using the Overlap Gap Property of almost optimal independent sets in random graphs, and the locality of the QAOA, we are able to show that if p is less than a d-dependent constant times log n, the QAOA cannot do better than finding an independent set of size .854 times the optimal for d large. Because the logarithm is slowly growing, even at one million qubits we can only show that the algorithm is blocked if p is in single digits. At higher p the algorithm sees the whole graph and we have no indication that performance is limited.
rate research
Read More
The performance of the quantum approximate optimization algorithm is evaluated by using three different measures: the probability of finding the ground state, the energy expectation value, and a ratio closely related to the approximation ratio. The set of problem instances studied consists of weighted MaxCut problems and 2-satisfiability problems. The Ising model representations of the latter possess unique ground states and highly-degenerate first excited states. The quantum approximate optimization algorithm is executed on quantum computer simulators and on the IBM Q Experience. Additionally, data obtained from the D-Wave 2000Q quantum annealer is used for comparison, and it is found that the D-Wave machine outperforms the quantum approximate optimization algorithm executed on a simulator. The overall performance of the quantum approximate optimization algorithm is found to strongly depend on the problem instance.
The next few years will be exciting as prototype universal quantum processors emerge, enabling implementation of a wider variety of algorithms. Of particular interest are quantum heuristics, which require experimentation on quantum hardware for their evaluation, and which have the potential to significantly expand the breadth of quantum computing applications. A leading candidate is Farhi et al.s Quantum Approximate Optimization Algorithm, which alternates between applying a cost-function-based Hamiltonian and a mixing Hamiltonian. Here, we extend this framework to allow alternation between more general families of operators. The essence of this extension, the Quantum Alternating Operator Ansatz, is the consideration of general parametrized families of unitaries rather than only those corresponding to the time-evolution under a fixed local Hamiltonian for a time specified by the parameter. This ansatz supports the representation of a larger, and potentially more useful, set of states than the original formulation, with potential long-term impact on a broad array of application areas. For cases that call for mixing only within a desired subspace, refocusing on unitaries rather than Hamiltonians enables more efficiently implementable mixers than was possible in the original framework. Such mixers are particularly useful for optimization problems with hard constraints that must always be satisfied, defining a feasible subspace, and soft constraints whose violation we wish to minimize. More efficient implementation enables earlier experimental exploration of an alternating operator approach to a wide variety of approximate optimization, exact optimization, and sampling problems. Here, we introduce the Quantum Alternating Operator Ansatz, lay out design criteria for mixing operators, detail mappings for eight problems, and provide brief descriptions of mappings for diverse problems.
Buhrman, Cleve and Wigderson (STOC98) observed that for every Boolean function $f : {-1, 1}^n to {-1, 1}$ and $bullet : {-1, 1}^2 to {-1, 1}$ the two-party bounded-error quantum communication complexity of $(f circ bullet)$ is $O(Q(f) log n)$, where $Q(f)$ is the bounded-error quantum query complexity of $f$. Note that the bounded-error randomized communication complexity of $(f circ bullet)$ is bounded by $O(R(f))$, where $R(f)$ denotes the bounded-error randomized query complexity of $f$. Thus, the BCW simulation has an extra $O(log n)$ factor appearing that is absent in classical simulation. A natural question is if this factor can be avoided. H{o}yer and de Wolf (STACS02) showed that for the Set-Disjointness function, this can be reduced to $c^{log^* n}$ for some constant $c$, and subsequently Aaronson and Ambainis (FOCS03) showed that this factor can be made a constant. That is, the quantum communication complexity of the Set-Disjointness function (which is $mathsf{NOR}_n circ wedge$) is $O(Q(mathsf{NOR}_n))$. Perhaps somewhat surprisingly, we show that when $ bullet = oplus$, then the extra $log n$ factor in the BCW simulation is unavoidable. In other words, we exhibit a total function $F : {-1, 1}^n to {-1, 1}$ such that $Q^{cc}(F circ oplus) = Theta(Q(F) log n)$. To the best of our knowledge, it was not even known prior to this work whether there existed a total function $F$ and 2-bit function $bullet$, such that $Q^{cc}(F circ bullet) = omega(Q(F))$.
Quantum variational algorithms have garnered significant interest recently, due to their feasibility of being implemented and tested on noisy intermediate scale quantum (NISQ) devices. We examine the robustness of the quantum approximate optimization algorithm (QAOA), which can be used to solve certain quantum control problems, state preparation problems, and combinatorial optimization problems. We demonstrate that the error of QAOA simulation can be significantly reduced by robust control optimization techniques, specifically, by sequential convex programming (SCP), to ensure error suppression in situations where the source of the error is known but not necessarily its magnitude. We show that robust optimization improves both the objective landscape of QAOA as well as overall circuit fidelity in the presence of coherent errors and errors in initial state preparation.
The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm which offers the potential to handle combinatorial optimization problems. Introducing constraints in such combinatorial optimization problems poses a major challenge in the extensions of QAOA to support relevant larger scale problems. In this paper, we introduce a quantum machine learning approach to learn the mixer Hamiltonian that is required to hard constrain the search subspace. We show that this method can be used for encoding any general form of constraints. By using a form of an adaptable ansatz, one can directly plug the learnt unitary into the QAOA framework. This procedure gives the flexibility to control the depth of the circuit at the cost of accuracy of enforcing the constraint, thus having immediate application in the Noisy Intermediate Scale Quantum (NISQ) era. We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constrains. Finally using this metric, we evaluate the performance of the proposed algorithm.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
