Quantum optimization algorithms
Different optimization techniques are applied in various fields such as mechanics, economics and engineering, and as the complexity and amount of data involved rise, more efficient ways of solving optimization problems are needed.The fit's quality is measured by some criteria, usually the distance between the function and the data points.One of the most common types of data fitting is solving the least squares problem, minimizing the sum of the squares of differences between the data points and the fitted function.is defined to be the following matrix: The quantum least-squares fitting algorithm[2] makes use of a version of Harrow, Hassidim, and Lloyd's quantum algorithm for linear systems of equations (HHL), and outputs the coefficientsis sparse and the condition number (namely, the ratio between the largest and the smallest eigenvalues) of bothSemidefinite programming (SDP) is an optimization subfield dealing with the optimization of a linear objective function (a user-specified function to be minimized or maximized), over the intersection of the cone of positive semidefinite matrices with an affine space.must lie in the (closed convex) cone of positive semidefinite symmetric matricesFinally, the SDP problem can be written as: The best classical algorithm is not known to unconditionally run in polynomial time.In each iteration, it solves a feasibility problem, namely, finds any solution satisfying the following conditions (giving a thresholdThe algorithm performs a binary search to find the minimal threshold[8] The relative speed-up of the quantum algorithm is an open research question.In each iteration, the state is measured in the computational basis and the Boolean functionA sample circuit that implements QAOA on a quantum computer is given in figure.This procedure is highlighted using the following example of finding the minimum vertex cover of a graph.For example, the bit string 0101 represents a cover consisting of the second and fourth vertex in a graph with four vertices.The goal of the algorithm is to sample these bit strings with high probability.In this case, the cost Hamiltonian has two ground states, |1010⟩ and |0110⟩, coinciding with the solutions of the problem.The mixer Hamiltonian is the simple, non-commuting sum of Pauli-X operations on each node of the graph and they are given by:Implementing QAOA algorithm for this four qubit circuit with two layers of the ansatz in qiskit (see figure) and optimizing leads to a probability distribution for the states given in the figure.can be reached up to arbitrary precision, this is guaranteed by the adiabatic theorem[10][11] or alternatively by the universality of the QAOA unitaries.For example, it was shown that QAOA exhibits a strong dependence on the ratio of a problem's constraint to variables (problem density) placing a limiting restriction on the algorithm's capacity to minimize a corresponding objective function.[13] It was soon recognized that a generalization of the QAOA process is essentially an alternating application of a continuous-time quantum walk on an underlying graph followed by a quality-dependent phase shift applied to each solution state.This generalized QAOA was termed as QWOA (Quantum Walk-based Optimisation Algorithm).[14] In the paper How many qubits are needed for quantum computational supremacy submitted to arXiv,[15] the authors conclude that a QAOA circuit with 420 qubits and 500 constraints would require at least one century to be simulated using a classical simulation algorithm running on state-of-the-art supercomputers so that would be sufficient for quantum computational supremacy.A rigorous comparison of QAOA with classical algorithms can give estimates on depthHowever, ansatz design must balance specificity and generality to avoid overfitting and maintain applicability to a wide range of problems.For this reason, designing optimal ansatze for QAOA is an extensively researched and widely investigated topic.Some of the proposed variants are: Another variation of QAOA focuses on techniques for parameter optimization, which aims at selecting the optimal set of initial parameters for a given problem and avoiding barren plateaus, which represent parameters leading to eigenstates which correspond to plateaus in the energy landscape of the cost Hamiltonian.Finally, there has been significant research interest in leveraging specific hardware to enhance the performance of QAOA across various platforms, such as trapped ion, neutral atoms, superconducting qubits, and photonic quantum computers.The goals of these approaches include overcoming hardware connectivity limitations and mitigating noise-related issues to broaden the applicability of QAOA to a wide range of combinatorial optimization problems.
quantum algorithmsMathematical optimizationmechanicseconomicsengineeringQuantum computingData fittingmathematical functionleast squarescontinuous functionslinear combinationcomplexquantum algorithm for linear systems of equationsinversesparsecondition numbereigenvaluesSemidefinite programmingobjective functionpositive semidefinite matricesaffine spaceinner productpolynomial timebinary searchcombinatorial optimizationfinite setBoolean functionsApproximate optimizationNP-hardQuantum Adiabatic theoremunitary operatorsanglesquantum superpositionminimum vertex coverPauli-Xconstraintvariablesqubitsconstraintsstate-of-the-artsupercomputersquantum computational supremacyMaxCutAdiabatic quantum computationQuantum annealingBibcodenpj Quantum InformationSvore, KrystaO'Donnell, RyanQuantum information scienceDiVincenzo's criteriaNISQ eratimelineQuantum informationQuantum programmingQuantum simulationphysical vs. logicalQuantum processorscloud-basedBell'sEastin–KnillGleason'sGottesman–KnillHolevo'sNo-broadcastingNo-cloningNo-communicationNo-deletingNo-hidingNo-teleportationQuantum speed limitThresholdSolovay–KitaevPurificationClassical capacityentanglement-assistedquantum capacityEntanglement distillationMonogamy of entanglementQuantum channelquantum networkQuantum teleportationquantum gate teleportationSuperdense codingQuantum cryptographyPost-quantum cryptographyQuantum coin flippingQuantum moneyQuantum key distributionSARG04other protocolsQuantum secret sharingAmplitude amplificationBernstein–VaziraniBoson samplingDeutsch–JozsaGrover'sHidden subgroupQuantum countingQuantum Fourier transformQuantum phase estimationShor'sSimon'sQuantumcomplexity theoryPostBQPQuantum supremacyQuantum volumeRandomized benchmarkingRelaxation timescomputing modelsContinuous-variable quantum informationOne-way quantum computercluster stateQuantum circuitquantum logic gateQuantum machine learningquantum neural networkQuantum Turing machineTopological quantum computerQuantumerror correctionquantum convolutionalstabilizerBacon–ShorSteaneQuantum opticsCavity QED