 Award ID(s):
 1937008
 NSFPAR ID:
 10316458
 Date Published:
 Journal Name:
 Algorithms
 Volume:
 14
 Issue:
 10
 ISSN:
 19994893
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Chakraborty, Supratik ; Jiang, JieHong Roland (Ed.)Quantum Computing (QC) is a new computational paradigm that promises significant speedup over classical computing in various domains. However, nearterm QC faces numerous challenges, including limited qubit connectivity and noisy quantum operations. To address the qubit connectivity constraint, circuit mapping is required for executing quantum circuits on quantum computers. This process involves performing initial qubit placement and using the quantum SWAP operations to relocate nonadjacent qubits for nearestneighbor interaction. Reducing the SWAP count in circuit mapping is essential for improving the success rate of quantum circuit execution as SWAPs are costly and errorprone. In this work, we introduce a novel circuit mapping method by combining incremental and parallel solving for Boolean Satisfiability (SAT). We present an innovative SAT encoding for circuit mapping problems, which significantly improves solverbased mapping methods and provides a smooth tradeoff between compilation quality and compilation time. Through comprehensive benchmarking of 78 instances covering 3 quantum algorithms on 2 distinct quantum computer topologies, we demonstrate that our method is 26× faster than stateoftheart solverbased methods, reducing the compilation time from hours to minutes for important quantum applications. Our method also surpasses the existing heuristics algorithm by 26% in SWAP count.more » « less

Abstract The SAT problem is a prototypical NPcomplete problem of fundamental importance in computational complexity theory with many applications in science and engineering; as such, it has long served as an essential benchmark for classical and quantum algorithms. This study shows numerical evidence for a quadratic speedup of the Grover Quantum Approximate Optimization Algorithm (GQAOA) over random sampling for finding all solutions to 3SAT (AllSAT) and MaxSAT problems. GQAOA is less resourceintensive and more adaptable for these problems than Grover’s algorithm, and it surpasses conventional QAOA in its ability to sample all solutions. We show these benefits by classical simulations of manyround GQAOA on thousands of random 3SAT instances. We also observe GQAOA advantages on the IonQ Aria quantum computer for small instances, finding that current hardware suffices to determine and sample all solutions. Interestingly, a singleanglepair constraint that uses the same pair of angles at each GQAOA round greatly reduces the classical computational overhead of optimizing the GQAOA angles while preserving its quadratic speedup. We also find parameter clustering of the angles. The singleanglepair protocol and parameter clustering significantly reduce obstacles to classical optimization of the GQAOA angles.

Abstract Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with nearterm quantum computers. As there are no algorithmic guarantee possible for QAOA to outperform classical computers, without a proof that boundederror quantum polynomial time (BQP) ≠ nondeterministic polynomial time (NP), it is necessary to investigate the empirical advantages of QAOA. We identify a computational phase transition of QAOA when solving hard problems such as SAT—random instances are most difficult to train at a critical problem density. We connect the transition to the controllability and the complexity of QAOA circuits. Moreover, we find that the critical problem density in general deviates from the SATUNSAT phase transition, where the hardest instances for classical algorithms lies. Then, we show that the high problem density region, which limits QAOA’s performance in hard optimization problems (reachability deficits), is actually a good place to utilize QAOA: its approximation ratio has a much slower decay with the problem density, compared to classical approximate algorithms. Indeed, it is exactly in this region that quantum advantages of QAOA over classical approximate algorithms can be identified.

Santhanam, Rahul (Ed.)Depth3 circuit lower bounds and kSAT algorithms are intimately related; the stateoftheart Σ^k_3circuit lower bound (OrAndOr circuits with bottom fanin at most k) and the kSAT algorithm of Paturi, Pudlák, Saks, and Zane (J. ACM'05) are based on the same combinatorial theorem regarding kCNFs. In this paper we define a problem which reveals new interactions between the two, and suggests a concrete approach to significantly stronger circuit lower bounds and improved kSAT algorithms. For a natural number k and a parameter t, we consider the Enum(k, t) problem defined as follows: given an nvariable kCNF and an initial assignment α, output all satisfying assignments at Hamming distance t(n) of α, assuming that there are no satisfying assignments of Hamming distance less than t(n) of α. We observe that an upper bound b(n, k, t) on the complexity of Enum(k, t) simultaneously implies depth3 circuit lower bounds and kSAT algorithms:  Depth3 circuits: Any Σ^k_3 circuit computing the Majority function has size at least binom(n,n/2)/b(n, k, n/2).  kSAT: There exists an algorithm solving kSAT in time O(∑_{t=1}^{n/2}b(n, k, t)). A simple construction shows that b(n, k, n/2) ≥ 2^{(1  O(log(k)/k))n}. Thus, matching upper bounds for b(n, k, n/2) would imply a Σ^k_3circuit lower bound of 2^Ω(log(k)n/k) and a kSAT upper bound of 2^{(1  Ω(log(k)/k))n}. The former yields an unrestricted depth3 lower bound of 2^ω(√n) solving a long standing open problem, and the latter breaks the Super Strong Exponential Time Hypothesis. In this paper, we propose a randomized algorithm for Enum(k, t) and introduce new ideas to analyze it. We demonstrate the power of our ideas by considering the first nontrivial instance of the problem, i.e., Enum(3, n/2). We show that the expected running time of our algorithm is 1.598ⁿ, substantially improving on the trivial bound of 3^{n/2} ≃ 1.732ⁿ. This already improves Σ^3_3 lower bounds for Majority function to 1.251ⁿ. The previous bound was 1.154ⁿ which follows from the work of Håstad, Jukna, and Pudlák (Comput. Complex.'95). By restricting ourselves to monotone CNFs, Enum(k, t) immediately becomes a hypergraph Turán problem. Therefore our techniques might be of independent interest in extremal combinatorics.more » « less

We compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with stateoftheart classical solvers Gurobi and MQLib to solve the MaxCut problem on 3regular graphs. We identify the minimum noiseless sampling frequency and depthmore » « less
p required for a quantum device to outperform classical algorithms. There is potential for quantum advantage on hundreds of qubits and moderate depth with a sampling frequency of 10 kHz. We observe, however, that classical heuristic solvers are capable of producing highquality approximate solutions in linear time complexity. In order to match this quality for large graph sizesN , a quantum device must support depthp > 11. Additionally, multishot QAOA is not efficient on large graphs, indicating that QAOAp ≤ 11 does not scale withN . These results limit achieving quantum advantage for QAOA MaxCut on 3regular graphs. Other problems, such as different graphs, weighted MaxCut, and 3SAT, may be better suited for achieving quantum advantage on nearterm quantum devices.