We develop the theory of the edge coloring of lattice graphs. A central role is played by a necessary and sufficient condition for a proper edge coloring of a patch of a lattice graph to induce a proper edge coloring of the entire lattice graph by translation. Using this condition, we introduce a method that finds nearly minimal or minimal edge colorings of lattice graphs. For a nearly minimal edge coloring, the running time is O(μ2D4), where μ is the number of edges in one cell (or “basis graph”) of the lattice graph and D is the maximum distance between two cells connected by an edge. Crucially, this complexity depends only on local properties of the lattice graph, making it independent of the total graph size. As a result, the method applies even to infinite lattice graphs with finite maximum degree. For minimal edge coloring, we lack a rigorous upper bound on the running time, which we find poses no limitation in practice; we use the method to minimally edge color the meshes of all k-uniform tilings of the plane for k ≤ 6 with modest computational resources. We find that all these lattice graphs belong to Vizing class I. By relating edge colorings to quantum circuits, our work has direct applications in quantum computation, including quantum simulation of condensed matter, cluster-state preparation, error characterization, and error correction.
We develop the theory of the edge coloring of lattice graphs. A central role is played by a necessary and sufficient condition for a proper edge coloring of a patch of a lattice graph to induce a proper edge coloring of the entire lattice graph by translation. Using this condition, we introduce a method that finds nearly minimal or minimal edge colorings of lattice graphs. For a nearly minimal edge coloring, the running time is O(μ2D4), where μ is the number of edges in one cell (or “basis graph”) of the lattice graph and D is the maximum distance between two cells connected by an edge. Crucially, this complexity depends only on local properties of the lattice graph, making it independent of the total graph size. As a result, the method applies even to infinite lattice graphs with finite maximum degree. For minimal edge coloring, we lack a rigorous upper bound on the running time, which we find poses no limitation in practice; we use the method to minimally edge color the meshes of all k-uniform tilings of the plane for k ≤ 6 with modest computational resources. We find that all these lattice graphs belong to Vizing class I. By relating edge colorings to quantum circuits, our work has direct applications in quantum computation, including quantum simulation of condensed matter, cluster-state preparation, error characterization, and error correction.
Given a graph G with n vertices and maximum degree Δ, it is known that G admits a vertex coloring with Δ+1 colors such that no edge of G is monochromatic. This can be seen constructively by a simple greedy algorithm, which runs in time O(nΔ). Very recently, a sequence of results (e.g., [Assadi et. al. SODA'19, Bera et. al. ICALP'20, Alon Assadi Approx/Random'20]) show randomized algorithms for (ε+1)Δ-coloring in the query model making O~(nn) queries, improving over the greedy strategy on dense graphs. In addition, a lower bound of Ω(nn) for any O(Δ)-coloring is established on general graphs. In this work, we give a simple algorithm for (1+ε)Δ-coloring. This algorithm makes O(ε−1/2nn) queries, which matches the best existing algorithms as well as the classical lower bound for sufficiently large ε. Additionally, it can be readily adapted to a quantum query algorithm making O~(ε−1n4/3) queries, bypassing the classical lower bound. Complementary to these algorithmic results, we show a quantum lower bound of Ω(n) for O(Δ)-coloring.
Let U be a universe on n elements, let k be a positive integer, and let ℱ be a family of (implicitly defined) subsets of U. We consider the problems of partitioning U into k sets from ℱ, covering U with k sets from ℱ, and packing k non-intersecting sets from ℱ into U. Classically, these problems can be solved via inclusion-exclusion in 2ⁿ n^O(1) time [Andreas Björklund et al., 2009]. Quantumly, there are faster algorithms for graph coloring with running time O(1.9140ⁿ) [Kazuya Shimizu and Ryuhei Mori, 2022] and for Set Cover with a small number of sets with running time O(1.7274ⁿ |ℱ|^O(1)) [Andris Ambainis et al., 2019]. In this paper, we give a quantum speedup for Set Partition, Set Cover, and Set Packing whenever there is a classical enumeration algorithm that lends itself to a quadratic quantum speedup, which, for any subinstance on a set X ⊆ U, enumerates at least one member of a k-partition, k-cover, or k-packing (if one exists) restricted to (or projected onto, in the case of k-cover) the set X in c^|X| n^O(1) time with c < 2. Our bounded-error quantum algorithm runs in time (2+c)^{n/2} n^O(1) for Set Partition, Set Cover, and Set Packing. It is obtained by combining three algorithms that have the best running time for some values of c. When c ≤ 1.147899, our algorithm is slightly faster than (2+c)^{n/2} n^O(1); when c approaches 1, it matches the O(1.7274ⁿ |ℱ|^O(1)) running time of [Andris Ambainis et al., 2019] for Set Cover when |ℱ| is subexponential in n. For covering, packing, and partitioning into maximal independent sets, maximal cliques, maximal bicliques, maximal cluster graphs, maximal triangle-free graphs, maximal cographs, maximal claw-free graphs, maximal trivially-perfect graphs, maximal threshold graphs, maximal split graphs, maximal line graphs, and maximal induced forests, we obtain bounded-error quantum algorithms with running times ranging from O(1.8554ⁿ) to O(1.9629ⁿ). Packing and covering by maximal induced matchings can be done quantumly in O(1.8934ⁿ) time. For Graph Coloring (covering with k maximal independent sets), we further improve the running time to O(1.7956ⁿ) by leveraging faster algorithms for coloring with a small number of colors to better balance our divide-and-conquer steps. For Domatic Number (packing k minimal dominating sets), we obtain a O((2-ε)ⁿ) running time for some ε > 0. Several of our results should be of interest to proponents of classical computing: - We present an inclusion-exclusion algorithm with running time O^*(∑_{i=0}^⌊αn⌋ binom(n,i)), which determines, for each X ⊆ U of size at most α n, 0 ≤ α ≤ 1, whether (X,ℱ) has a k-cover, k-partition, or k-packing. This running time is best-possible, up to polynomial factors. - We prove that for any linear-sized vertex subset X ⊆ V of a graph G = (V,E), the number of minimal dominating sets of G that are subsets of X is O((2-ε)^|X|) for some ε > 0.
This paper introduces an efficient quantum computing method for reducing special graphs in the context of the graph coloring problem. The special graphs considered include both symmetric and non-symmetric graphs where the axis passes through nodes only, edges only, and both together. The presented method reduces the number of coloring matrices, which is important for realization of the number of quantum states required, from KN to K2N+m upon one symmetric reduction of graphs symmetric about an axis passing through m nodes, where K is the number of colours required and \emph{N} being total number of nodes. Similarly for other types also, the number of quantum states is reduced. The complexity in the number of qubits has been reduced by δCq=89N2−83m2−43Nm−4N+4m upon one symmetric reduction of graphs, symmetric about an axis passing through m nodes and other types as presented in the paper. Additionally, the number of gates and number of iterations are reduced massively compared to state-of-the-art quantum algorithms. Like for a graph with 20 nodes and symmetric line passing through 2 nodes, the number of iterations decreased from 5157 to 67. Therefore, the procedure presented for solving the graph coloring problem now requires a significantly reduced number of qubits compared to before. The run time of the proposed algorithm for these special type of graphs are reduced from O(1.9575N) to O(1.9575(2N+m)) upon one symmetric reduction of graphs symmetric about an axis passing through m nodes and similarly for others cases.
Genetic algorithms (GA) are computational methods for solving optimization problems inspired by natural selection. Because we can simulate the quantum circuits that implement GA in different highly configurable noise models and even run GA on actual quantum computers, we can analyze this class of heuristic methods in the quantum context for NP-hard problems. This paper proposes an instantiation of the Reduced Quantum Genetic Algorithm (RQGA) that solves the NP-hard graph coloring problem in O(N 1/2 ). The proposed implementation solves both vertex and edge coloring and can also determine the chromatic number ( i.e ., the minimum number of colors required to color the graph). We examine the results, analyze the algorithm convergence, and measure the algorithm's performance using the Qiskit simulation environment. Our Reduced Quantum Genetic Algorithm (RQGA) circuit implementation and the graph coloring results show that quantum heuristics can tackle complex computational problems more efficiently than their conventional counterparts.
In this paper, a new type of edge coloring of graphs together with an algorithm for such an edge coloring is presented to construct some column-weight three low-density parity-check (LDPC) codes whose Tanner graphs are free of 4-cycles. This kind of edge coloring is applied on some well-known classes of graphs such as complete graphs and complete bipartite graphs to generate some column-weight 3 LDPC codes having flexibility in terms of code length and rate. Interestingly, the constructed (3, k)-regular codes with regularities k = 4, 5,..., 22 have lengths n = 12, 20, 26, 35, 48, 57, 70, 88, 104, 117, 140, 155, 176, 204, 228, 247, 280, 301, 330, having minimum block length compared to the best known similar codes in the literature. In addition to linear complexity of generating such parity-check matrices, they can be considered as the base matrices of some quasi-cyclic (QC) LDPC codes with maximum achievable girth 18, which inherit the low-complexity encoder implementations of QC-LDPC codes. Simulation results show that the QC-LDPC codes with large girth lifted from the constructed base matrices have good performances and outperform random codes, progressive edge growth LDPC codes, some finite fields and group rings based QC-LDPC codes and also have a close competition to the standard IEEE 802. 16e (WiMAX) code.
Probing energy-dependent transport in quantum simulators requires preparing states with tunable energy and small energy variance. Existing approaches often study quench dynamics of simple initial states, such as computational basis states, which are far from energy eigenstates and therefore limit the achievable energy resolution. In this work, we propose using wavepackets to probe transport properties with improved energy resolution. To demonstrate the utility of this approach, we prepare and evolve wavepackets on Quantinuum's H2-2 quantum computer and identify an energy-dependent localization transition in the Anderson model on an 8x7 lattice--a finite-size mobility edge. We observe that a wavepacket initialized at low energy remains spatially localized under time evolution, while a high-energy wavepacket delocalizes, consistent with the presence of a mobility edge. Crucial to our experiments is an error mitigation strategy that infers the noiseless output bit string distribution using maximum-likelihood estimation. Compared to post-selection, this method removes systematic errors and reduces statistical uncertainty by up to a factor of 5. We extend our methods to the many-particle regime by developing a quantum algorithm for preparing quasiparticle wavepackets in a one-dimensional model of interacting fermions. This technique has modest quantum resource requirements, making wavepacket-based studies of transport in many-body systems a promising application for near-term quantum computers.