Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAnalytical Framework for Quantum Alternating Operator Ansatze
64
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We develop a framework for analyzing layered quantum algorithms such as quantum alternating operator ansatze. Our framework relates quantum cost gradient operators, derived from the cost and mixing Hamiltonians, to classical cost difference functions that reflect cost function neighborhood structure. By considering QAOA circuits from the Heisenberg picture, we derive exact general expressions for expectation values as series expansions in the algorithm parameters, cost gradient operators, and cost difference functions. This enables novel interpretability and insight into QAOA behavior in various parameter regimes. For single- level QAOA1 we show the leading-order changes in the output probabilities and cost expectation value explicitly in terms of classical cost differences, for arbitrary cost functions. This demonstrates that, for sufficiently small positive parameters, probability flows from lower to higher cost states on average. By selecting signs of the parameters, we can control the direction of flow. We use these results to derive a classical random algorithm emulating QAOA1 in the small-parameter regime, i.e., that produces bitstring samples with the same probabilities as QAOA1 up to small error. For deeper QAOAp circuits we apply our framework to derive analogous and additional results in several settings. In particular we show QAOA always beats random guessing. We describe how our framework incorporates cost Hamiltonian locality for specific problem classes, including causal cone approaches, and applies to QAOA performance analysis with arbitrary parameters. We illuminate our results with a number of examples including applications to QUBO problems, MaxCut, and variants of MaxSat. We illustrate the application to QAOA circuits using mixing unitaries beyond the transverse-field mixer through two examples of constrained optimization, Max Independent Set and Graph Coloring.
rate research
Read More
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 large 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.
Determining Hamiltonian ground states and energies is a challenging task with many possible approaches on quantum computers. While variational quantum eigensolvers are popular approaches for near term hardware, adiabatic state preparation is an alternative that does not require noisy optimization of parameters. Beyond adiabatic schedules, QAOA is an important method for optimization problems. In this work we modify QAOA to apply to finding ground states of molecules and empirically evaluate the modified algorithm on several molecules. This modification applies physical insights used in classical approximations to construct suitable QAOA operators and initial state. We find robust qualitative behavior for QAOA as a function of the number of steps and size of the parameters, and demonstrate this behavior also occurs in standard QAOA applied to combinatorial search. To this end we introduce QAOA phase diagrams that capture its performance and properties in various limits. In particular we show a region in which non-adiabatic schedules perform better than the adiabatic limit while employing lower quantum circuit depth. We further provide evidence our results and insights also apply to QAOA applications beyond chemistry.
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.
In this paper we introduce a universal operator theoretic framework for quantum fault tolerance. This incorporates a top-down approach that implements a system-level criterion based on specification of the full system dynamics, applied at every level of error correction concatenation. This leads to more accurate determinations of error thresholds than could previously be obtained. This is demonstrated both formally and with an explicit numerical example. The basis for our approach is the Quantum Computer Condition (QCC), an inequality governing the evolution of a quantum computer. We show that all known coding schemes are actually special cases of the QCC. We demonstrate this by introducing a new, operator theoretic form of entanglement assisted quantum error correction, which incorporates as special cases all known error correcting protocols, and is itself a special case of the QCC.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
