More Like this

1. Constrained quantum optimization for extractive summarization on a trapped-ion quantum computer

   https://doi.org/10.1038/s41598-022-20853-w  

   Niroula, Pradeep ; Shaydulin, Ruslan ; Yalovetzky, Romina ; Minssen, Pierre ; Herman, Dylan ; Hu, Shaohan ; Pistoia, Marco ( October 2022 , Scientific Reports)

   Realizing the potential of near-term quantum computers to solve industry-relevant constrained-optimization problems is a promising path to quantum advantage. In this work, we consider the extractive summarization constrained-optimization problem and demonstrate the largest-to-date execution of a quantum optimization algorithm that natively preserves constraints on quantum hardware. We report results with the Quantum Alternating Operator Ansatz algorithm with a Hamming-weight-preserving XY mixer (XY-QAOA) on trapped-ion quantum computer. We successfully execute XY-QAOA circuits that restrict the quantum evolution to the in-constraint subspace, using up to 20 qubits and a two-qubit gate depth of up to 159. We demonstrate the necessity of directly encoding the constraints into the quantum circuit by showing the trade-off between the in-constraint probability and the quality of the solution that is implicit if unconstrained quantum optimization methods are used. We show that this trade-off makes choosing good parameters difficult in general. We compare XY-QAOA to the Layer Variational Quantum Eigensolver algorithm, which has a highly expressive constant-depth circuit, and the Quantum Approximate Optimization Algorithm. We discuss the respective trade-offs of the algorithms and implications for their execution on near-term quantum hardware.
2. How many qubits are needed for quantum computational supremacy?

   https://doi.org/10.22331/q-2020-05-11-264  

   Dalzell, Alexander M. ; Harrow, Aram W. ; Koh, Dax Enshan ; La Placa, Rolando L. ( May 2020 , Quantum)

   Quantum computational supremacy arguments, which describe a way for a quantum computer to perform a task that cannot also be done by a classical computer, typically require some sort of computational assumption related to the limitations of classical computation. One common assumption is that the polynomial hierarchy ( P H ) does not collapse, a stronger version of the statement that P ≠ N P , which leads to the conclusion that any classical simulation of certain families of quantum circuits requires time scaling worse than any polynomial in the size of the circuits. However, the asymptotic nature of this conclusion prevents us from calculating exactly how many qubits these quantum circuits must have for their classical simulation to be intractable on modern classical supercomputers. We refine these quantum computational supremacy arguments and perform such a calculation by imposing fine-grained versions of the non-collapse conjecture. Our first two conjectures poly3-NSETH( a ) and per-int-NSETH( b ) take specific classical counting problems related to the number of zeros of a degree-3 polynomial in n variables over F 2 or the permanent of an n × n integer-valued matrix, and assert that any non-deterministic algorithm that solves them requires 2 c nmore »time steps, where c ∈ { a , b } . A third conjecture poly3-ave-SBSETH( a ′ ) asserts a similar statement about average-case algorithms living in the exponential-time version of the complexity class S B P . We analyze evidence for these conjectures and argue that they are plausible when a = 1 / 2 , b = 0.999 and a ′ = 1 / 2 .Imposing poly3-NSETH(1/2) and per-int-NSETH(0.999), and assuming that the runtime of a hypothetical quantum circuit simulation algorithm would scale linearly with the number of gates/constraints/optical elements, we conclude that Instantaneous Quantum Polynomial-Time (IQP) circuits with 208 qubits and 500 gates, Quantum Approximate Optimization Algorithm (QAOA) circuits with 420 qubits and 500 constraints and boson sampling circuits (i.e. linear optical networks) with 98 photons and 500 optical elements are large enough for the task of producing samples from their output distributions up to constant multiplicative error to be intractable on current technology. Imposing poly3-ave-SBSETH(1/2), we additionally rule out simulations with constant additive error for IQP and QAOA circuits of the same size. Without the assumption of linearly increasing simulation time, we can make analogous statements for circuits with slightly fewer qubits but requiring 10 4 to 10 7 gates.« less
3. 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)

   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.
4. Analyzing the performance of variational quantum factoring on a superconducting quantum processor

   https://doi.org/10.1038/s41534-021-00478-z  

   Karamlou, Amir H. ; Simon, William A. ; Katabarwa, Amara ; Scholten, Travis L. ; Peropadre, Borja ; Cao, Yudong ( October 2021 , npj Quantum Information)

   In the near-term, hybrid quantum-classical algorithms hold great potential for outperforming classical approaches. Understanding how these two computing paradigms work in tandem is critical for identifying areas where such hybrid algorithms could provide a quantum advantage. In this work, we study a QAOA-based quantum optimization approach by implementing the Variational Quantum Factoring (VQF) algorithm. We execute experimental demonstrations using a superconducting quantum processor, and investigate the trade off between quantum resources (number of qubits and circuit depth) and the probability that a given biprime is successfully factored. In our experiments, the integers 1099551473989, 3127, and 6557 are factored with 3, 4, and 5 qubits, respectively, using a QAOA ansatz with up to 8 layers and we are able to identify the optimal number of circuit layers for a given instance to maximize success probability. Furthermore, we demonstrate the impact of different noise sources on the performance of QAOA, and reveal the coherent error caused by the residualZZ-coupling between qubits as a dominant source of error in a near-term superconducting quantum processor.
5. Sparse SYK and traversable wormholes

   https://doi.org/10.1007/JHEP11(2021)015  

   Cáceres, Elena ; Misobuchi, Anderson ; Pimentel, Rafael ( November 2021 , Journal of High Energy Physics)

   A bstract We investigate two sparse Sachdev-Ye-Kitaev (SYK) systems coupled by a bilinear term as a holographic quantum mechanical description of an eternal traversable wormhole in the low temperature limit. Each SYK system consists of N Majorana fermions coupled by random q -body interactions. The degree of sparseness is captured by a regular hypergraph in such a way that the Hamiltonian contains exactly k N independent terms. We improve on the theoretical understanding of the sparseness property by using known measures of hypergraph expansion. We show that the sparse version of the two coupled SYK model is gapped with a ground state close to a thermofield double state. Using Krylov subspace and parallelization techniques, we simulate the system for q = 4 and q = 8. The sparsity of the model allows us to explore larger values of N than the ones existing in the literature for the all-to-all SYK. We analyze in detail the two-point functions and the transmission amplitude of signals between the two systems. We identify a range of parameters where revivals obey the scaling predicted by holography and signals can be interpreted as traversing the wormhole.