More Like this

1. Quantum computational phase transition in combinatorial problems

   https://doi.org/10.1038/s41534-022-00596-2  

   Zhang, Bingzhi; Sone, Akira; Zhuang, Quntao (July 2022, npj Quantum Information)

   Abstract Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with near-term quantum computers. As there are no algorithmic guarantee possible for QAOA to outperform classical computers, without a proof that bounded-error 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 SAT-UNSAT 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. 

   more » « less
2. Grover-QAOA for 3-SAT: quadratic speedup, fair-sampling, and parameter clustering

   https://doi.org/10.1088/2058-9565/ad895c  

   Zhang, Zewen; Paredes, Roger; Sundar, Bhuvanesh; Quiroga, David; Kyrillidis, Anastasios; Duenas-Osorio, Leonardo; Pagano, Guido; Hazzard, Kaden_R_A (November 2024, Quantum Science and Technology)

   Abstract The SAT problem is a prototypical NP-complete 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 (G-QAOA) over random sampling for finding all solutions to 3-SAT (All-SAT) and Max-SAT problems. G-QAOA is less resource-intensive 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 many-round G-QAOA on thousands of random 3-SAT instances. We also observe G-QAOA advantages on the IonQ Aria quantum computer for small instances, finding that current hardware suffices to determine and sample all solutions. Interestingly, a single-angle-pair constraint that uses the same pair of angles at each G-QAOA round greatly reduces the classical computational overhead of optimizing the G-QAOA angles while preserving its quadratic speedup. We also find parameter clustering of the angles. The single-angle-pair protocol and parameter clustering significantly reduce obstacles to classical optimization of the G-QAOA angles. 

   more » « less
3. A Linear Time Algorithm for Quantum 2-SAT

   De Beaudrap, Niel; Gharibian, Sevag (January 2016, Conference on Computational Complexity)

   The Boolean constraint satisfaction problem 3-SAT is arguably the canonical NP-complete problem. In contrast, 2-SAT can not only be decided in polynomial time, but in fact in deterministic linear time. In 2006, Bravyi proposed a physically motivated generalization of k-SAT to the quantum setting, defining the problem "quantum k-SAT". He showed that quantum 2-SAT is also solvable in polynomial time on a classical computer, in particular in deterministic time O(n^4), assuming unit-cost arithmetic over a field extension of the rational numbers, where n is number of variables. In this paper, we present an algorithm for quantum 2-SAT which runs in linear time, i.e. deterministic time O(n+m) for n and m the number of variables and clauses, respectively. Our approach exploits the transfer matrix techniques of Laumann et al. [QIC, 2010] used in the study of phase transitions for random quantum 2-SAT, and bears similarities with both the linear time 2-SAT algorithms of Even, Itai, and Shamir (based on backtracking) [SICOMP, 1976] and Aspvall, Plass, and Tarjan (based on strongly connected components) [IPL, 1979]. 

   more » « less
4. Parameterized Approximation Scheme for Feedback Vertex Set

   https://doi.org/10.4230/LIPIcs.MFCS.2023.56  

   Jana, Satyabrata; Lokshtanov, Daniel; Mandal, Soumen; Rai, Ashutosh; Saurabh, Saket (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Leroux, Jérôme; Lombardy, Sylvain; Peleg, David (Ed.)

   Feedback Vertex Set (FVS) is one of the most studied vertex deletion problems in the field of graph algorithms. In the decision version of the problem, given a graph G and an integer k, the question is whether there exists a set S of at most k vertices in G such that G-S is acyclic. It is one of the first few problems which were shown to be NP-complete, and has been extensively studied from the viewpoint of approximation and parameterized algorithms. The best-known polynomial time approximation algorithm for FVS is a 2-factor approximation, while the best known deterministic and randomized FPT algorithms run in time 𝒪^*(3.460^k) and 𝒪^*(2.7^k) respectively. In this paper, we contribute to the newly established area of parameterized approximation, by studying FVS in this paradigm. In particular, we combine the approaches of parameterized and approximation algorithms for the study of FVS, and achieve an approximation guarantee with a factor better than 2 in randomized FPT running time, that improves over the best known parameterized algorithm for FVS. We give three simple randomized (1+ε) approximation algorithms for FVS, running in times 𝒪^*(2^{εk}⋅ 2.7^{(1-ε)k}), 𝒪^*(({(4/(1+ε))^{(1+ε)}}⋅{(ε/3)^ε})^k), and 𝒪^*(4^{(1-ε)k}) respectively for every ε ∈ (0,1). Combining these three algorithms, we obtain a factor (1+ε) approximation algorithm for FVS, which has better running time than the best-known (randomized) FPT algorithm for every ε ∈ (0, 1). This is the first attempt to look at a parameterized approximation of FVS to the best of our knowledge. Our algorithms are very simple, and they rely on some well-known reduction rules used for arriving at FPT algorithms for FVS. 

   more » « less
5. Polynomial Kernel for Interval Vertex Deletion

   https://doi.org/10.1145/3571075  

   Agrawal, Akanksha; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav (April 2023, ACM Transactions on Algorithms)

   Given a graphGand an integerk, theInterval Vertex Deletion (IVD)problem asks whether there exists a subsetS⊆V(G) of size at mostksuch thatG-Sis an interval graph. This problem is known to beNP-complete (according to Yannakakis at STOC 1978). Originally in 2012, Cao and Marx showed thatIVDis fixed parameter tractable: they exhibited an algorithm with running time 10^kn^O(1). The existence of a polynomial kernel forIVDremained a well-known open problem in parameterized complexity. In this article, we settle this problem in the affirmative. 

   more » « less