Depth Optimization of CZ, CNOT, and Clifford Circuits

We seek to develop better upper bound guarantees on the depth of quantum CZ gate, cnot gate, and Clifford circuits than those reported previously. We focus on the number of qubits n≤ 1 345 000 (de Brugière et al. , 2021), which represents the most practical use case. Our upper bound on the depth of CZ circuits is ⌊n/2+0.4993⋅log2(n)+3.0191⋅log(n)−10.9139⌋ , improving the best-known […]

A Grover Search-Based Algorithm for the List Coloring Problem

Graph coloring is a computationally difficult problem, and currently the best known classical algorithm for k -coloring of graphs on n vertices has runtimes Ω(2n) for k≥5 . The list coloring problem asks the following more general question: given a list of available colors for each vertex in a graph, does it admit a proper coloring? We propose a hybrid classical-quantum algorithm based […]