# Grover Fixed Point Search for QUBO

### Atithi Acharya, Ákos Nagy, Jaime Park, and Cindy Zhang

### Mentor: Alex Khan

#### Batch 2 Demo Day

#### Wednesday, August 9, 2023.

# Grover's Search Algorithm

- Built to find a marked state in database of unsorted unmarked ones.

- Done through iterative application of reflections.

- Quadratic speed up as $N$ increases.

### The Soufflé Problem

- Grover's struggles when the number of target states is unknown (the number of iterations is also unknown).

- With too few rotations, we "undercook" the state.

- Too many rotations and we "overcook" the state.

### Solution: Grover Fixed Point Search

- A generalization of Grover's Search Algorithm.

- Yoder–Low–Chuang (2014): Phases are added to the reflection oracles based on success probability.

- As the number of iterations increase, the probability of success can only increase.

- Eliminates the soufflé problem and maintains the quadratic speed up.

# Quadratic Unconstrained Binary Optimization (QUBO) problems

- Problem: given a quadratic (real-valued) function, $f$, on $n$ (classical) bits, find its maximum.

- Such a function is given by a symmetric $n$-by-$n$ matrix, $Q$, and a constant $c$. (WLOG: set $c = 0$.)

- MaxCut is QUBO with $Q = $ Graph Laplacian.

### Circuit design

- State Preparation: Equal superposition of solutions and ancillas

- Grover Oracle: Marks desired states with some phase adjusted based on the success probability

- Diffusion Operator: Amplifies marked state

- The last two steps are repeated for all angles $\alpha$ and $\beta$.

### Oracle Overview

- Digitize values into ancillas.

- Mark desired states (first ancilla becomes 1 when value is above or on threshold).

- Reset ancillas to threshold value.

- Based on Gilliam–Woerner–Gonciulea (2021): $S_t$ uses $O \left( \ln \left( m \right) \right)$ ancillas.

### Example: MaxCut

- For a graph, $G = (V, E)$, find $S \subset V$ so that
\begin{equation}
\mathrm{cut}_G (S) = \left| \left\{ (v, v^\prime) \in E : v \in S \: \& \: v^\prime \notin S \right\} \right|,
\end{equation}
is maximal.

- Recall that MaxCut is QUBO with $Q = $ Graph Laplacian.

### More about MaxCut

- MaxCut is NP-hard.

- We only have polynomial time MaxCut-approximations.

- Goemans–Williamson Algorithm: polynomial time algorithm to get a cut at least $\approx 88$% of MaxCut.

- Erdős–Edwards bound for the maximal cut of connected graphs:
\begin{equation}
\mathrm{MaxCut}_G \geqslant \tfrac{2 m + n - 1}{4}, \quad \left( n = |V|, \: m = |E| \right).
\end{equation}
Can be found in $O \left( n^4 \right)$ time.

### Results

- For graphs less than or equal to 20 verticies and with target probability $\geqslant 90$%, $l = 1, 2$ suffices.

- Simulation with the noise model of a modern, all-to-all connected Quantum Computer (IonQ's Harmony) suggests that the noise of either oracles destroys most of the results when $n \geqslant 6$.

- This all works for any QUBO problem with minimal modification.

- In fact, works for
*all* binary optimization problems (short term #1).

- Note: we pre-computed the exact ratios of marked states; in lieu of that, one can also use an
*adaptive version* (short term #2).

# Example

## Erdős–Rényi-graph with $p = 0.5$, $|V| = 20$, & $|E| = 101$

# Simulation without noise

vertices |
20 |

edges |
101 |

$\mathrm{MaxCut}$ |
66 |

Erdős–Edwards |
56 |

random chance |
13.98% |

$\delta$ |
0.93 |

Query complexity |
1 |

success probability |
80.89% |

expectation |
55.87 (+5.37) |

ancillas |
7 |

gate count |
8097 |

circuit depth |
4009 |

simulation time |
$\sim$ 2 minutes |

# cut distributions

### Future plans/ideas

- Benchmark against existing algorithms.

- Refine and study the adaptive variant.

- Math problem: given a QUBO instance, can we bound the ratio of
*good configurations* polynomially, from below?

- More sci-fi: This construction can be used as an (approximate) Grover mixer for QAOA.

- The oracle design can be used immediately for Threshold-QAOA (cf. Golden–Bärtschi–O’Malley–Eidenbenz, 2021).

### Thank you for your attention!