Extended Quantum Computing Patterns

How to utilize efficient approximations in quantum algorithms to improve the solution quality or speed up the computation?

For many computationally hard problems, efficient approximation algorithms exist. However, typical quantum algorithms neglect these approximations and valuable information remains unused as the quantum algorithm starts from a neutral position. As a result, deep quantum circuits may be required, which increases accumulative error rates, and more quantum resources may be required to solve a problem.

Moreover, current quantum devices are error-prone, thus, the depth of executable quantum circuits is limited. However, including approximations requires special care, as it can limit the quantum algorithm in an unintended way [Cain et al. 2022][Truger et al. 2024]. Also, changing the initial state may require additional adaptations of corresponding parts of the quantum circuit [Egger et al. 2021][Tate et al. 2023a].

Encode approximations into the initial state of quantum circuits, thereby biasing the initial quantum state towards viable solutions. Hence, a chain of algorithm executions as depicted in the solution sketch below is beneficial: First, an efficient algorithm is utilized to approximate a solution of a given problem instance. This can often be achieved at low cost on classical hardware. Then, the initial state \(|\psi\rangle\) of the subsequent quantum algorithm is biased toward the approximation and the algorithm is executed on a quantum device to obtain an improved solution.

The quantum algorithm employed in the second step utilizes the approximation as a starting point to improve upon. Due to the biased initial state, optimal solutions can be explored quicker and the solution quality achievable in a set amount of time may therefore increase. Moreover, this way the workload of the overall computation can be distributed to multiple devices, e.g., classical and quantum devices.

–

This pattern is a refinement of the Warm-Start pattern and related to the State Preparation patterns, e.g., Angle Encoding, since different encodings may be applied to prepare and bias the initial state of a quantum algorithm [Weigold et al. 2021a] [Weigold et al. 2021b]. Moreover, it can be applied with the VQA pattern and its refinements, such as the QAOA [Weigold et al. 2021a].

Egger et al. introduce a biased initial state for QAOA and the Maximum Cut problem (MaxCut) utilizing the classical Goemans-Williamson approximation algorithm [Egger et al. 2021]. Similarly, Tate et al. adapt QAOA for MaxCut with a Burer-Monteiro relaxation of the problem [Tate et al. 2023b]. QAOA was also adapted for a biased initial state for the Knapsack problem [van Dam et al. 2021]. Wang proposes a "classically-boosted" quantum algorithm for the Maximum 3-Satisfiability and Maximum Bisection problems based on biased initial states [Wang 2022]. Beisel et al. propose a workflow modeling construct facilitating the integration of warm-starts via biased initial states in VQAs [Beisel et al. 2023].