Quantum computers are no longer a purely theoretical concept – a first generation of quantum computers is already available to the public [1, 2]. These devicesdiffer considerably from classical computers as their central unit of information isnot a classical bit (which can be in a state of either zero or one), but a quantumbit (qubit). Because they are based on qubits, quantum computers are expectedto solve certain problems faster than their classical counterparts [3, 4]. Famousexamples for quantum algorithms that promise a theoretical linear or exponential speedup are Shor’s algorithm [5] for factoring prime numbers or the HHLalgorithm [6] for solving linear equations.However, as current devices still have severe hardware limitations, they arealso referred to as Noisy Intermediate Scale Quantum (NISQ) devices [7]. Measured by their number of qubits, these devices are of intermediate size (theycontain up to a few hundred qubits). Their noisy qubits are only stable for alimited amount of time. Due to their short lifespan, the number of operationsthat can be executed on a NISQ device is limited. As a consequence, the requiredoperations of many quantum algorithms exceed those of NISQ devices, or theycan only be executed for small problems. For example, recent experiments wereable to demonstrate Shor’s algorithm [5] for factoring small numbers such as 15or 21 [8]. Given the current state of hardware, Shor’s algorithm is one of manyalgorithms which will not be of much practical use in the near future.
e., nding the solution which minimizes or maximizes the objective function, is. To circumvent this diculty, heuristic approaches can be used in order to nd a solution whose value of the objective function is close to the maximum or minimum of the objective function. Solution: Like in VQA, an initial state |si is created (see Figure 5) and an ansatz is constructed based on a phase-separating operator U (C, ) and a mixing operator U (B, ) which depend on the parameter sets and . 2 (,1) State Prep.AlternatingOperator AnsatzMeasurement ClassicalComputer (,)EvaluateCost S(x) Quantum Computer |0 (,) U(,) |0 |0 U(,1) argmin,(,)Optimize,, 10 Weigold et al.
id: 94fc3e8967e26d921d74a1a5d616ce4f - page: 10
Fig. 5. Quantum Alternating Operator Ansatz. The initial state |si is assumed to be created in constant depth, which in general is not possible for some quantum states. For example, |si can be a state that represents one single solution. Alternatively, a superposition of suitable solutions can be created. The separating phase operator encodes the objective function and changes the phase of a computational basis state |yi according to C(y): U (C, ) |yi = f (y) |yi (5) For example, U (C, ) can be dened such that a phase shift is applied to |yi for every fullled clause. The mixing operator U (B, ) changes the amplitudes of the solutions. In particular, it must be possible to transition from any solution to every other solution, i.e., for every pair (|xi , |yi) of computational basis states within the problem domain there exist some parameter for which U (B, ) provides a transition between them. Therefore, this operator depends on the structure of the domain.
id: 75eb56c98acdece9b12ef2bf1319b69a - page: 11
The solution creates on a quantum computer the initial state |si and applies unitaries drawn from C() and B() in alternation. This results in the following state: |, i = U (B, p)U (C, p) . . . U (B, 1)U (C, 1) |si (6) where , can be initialized randomly at rst and p N is a hyper-parameter. Measurement then results in a single solution z for which C(z) can be evaluated. By sampling, the expectation value for , can be determined. Because |, i is a linear combination of computational basis states, its expectation value is Patterns For Hybrid Quantum Algorithms always smaller or equal to the objective function for the best solution z: hCi|,i = h, |C|, i = xz |zi xzf (z) |zi = |xz|2f (z) (cid:12) (cid:12) (cid:12) (cid:12) (cid:28) X (cid:29)
id: 9d2770c849c36355fd46a5d78efd58be - page: 11
X |xz|2f (z) = f (z) = Cmax X The expectation values of variations of the parameters can then be used to optimize the angles for optimizing the objective function and thus, update and . This is repeated until the termination condition is fullled (e.g a solution z is found for which C(z) is above a certain threshold).
id: 1b8ac8db7c3124438d3e364b02f6dcf8 - page: 12