A Generalized Quantum Branching Program

• URL: http://arxiv.org/abs/2307.11395v1
• Date: Fri, 21 Jul 2023 07:27:51 GMT
• Title: A Generalized Quantum Branching Program
• Authors: Debajyoti Bera and Tharrmashastha Sapv
• Abstract summary: We propose a quantum branching program model, referred to as GQBP, with the ability to query different variables in superposition. We show several equivalences, namely, between GQBP and AQBP, GQBP and NQBP, and GQBP and query complexities.
• Score: 0.5584060970507505
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Classical branching programs are studied to understand the space complexity of computational problems. Prior to this work, Nakanishi and Ablayev had separately defined two different quantum versions of branching programs that we refer to as NQBP and AQBP. However, none of them, to our satisfaction, captures the intuitive idea of being able to query different variables in superposition in one step of a branching program traversal. Here we propose a quantum branching program model, referred to as GQBP, with that ability. To motivate our definition, we explicitly give examples of GQBP for n-bit Deutsch-Jozsa, n-bit Parity, and 3-bit Majority with optimal lengths. We the show several equivalences, namely, between GQBP and AQBP, GQBP and NQBP, and GQBP and query complexities (using either oracle gates and a QRAM to query input bits). In way this unifies the different results that we have for the two earlier branching programs, and also connects them to query complexity. We hope that GQBP can be used to prove space and space-time lower bounds for quantum solutions to combinatorial problems.

Related papers

• Bosonic Quantum Computational Complexity [0.0]
  We lay foundations for such a research program. We introduce natural complexity classes and problems based on bosonic generalizations of BQP. We show that the problem of deciding the boundedness of the spectrum of a bosonic Hamiltonian is co-NP-hard.
  arXiv  Detail & Related papers  (2024-10-05T19:43:41Z)
• Quantum Query-Space Lower Bounds Using Branching Programs [0.18416014644193066]
  We show the first explicit query-space lower bound for our restricted version of GQBP. We then generalize the problem to show that the same bound holds for deciding between two strings with a constant Hamming distance. Our results produce an alternative proof of the $Omega(sqrtn)$-lower bound on the query complexity of any non-constant symmetric Boolean function.
  arXiv  Detail & Related papers  (2024-07-09T13:58:53Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• stateQIP = statePSPACE [0.15229257192293197]
  We study the relation between two such state classes:SDPPSPACE, and stateQIP. Our main result is the reverse inclusion, stateQIP $subseteq$ statePSPACE. We also show that optimal prover strategies for general quantum interactive protocols can be implemented in quantum space.
  arXiv  Detail & Related papers  (2023-01-18T19:00:17Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
  arXiv  Detail & Related papers  (2023-01-05T11:05:22Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement [0.0]
  Savitch's theorem states that NPSPACE computations can be simulated in PSPACE. We show that a quantum analogue of Savitch's theorem is unlikely to hold, as SQCMASPACE=NEXP. We show how to embed SQCMASPACE into the Sparse Separable Hamiltonian problem of [Chailloux, Sattath, 2012] (QMA(2)-complete for 1/poly promise gap)
  arXiv  Detail & Related papers  (2022-06-10T17:35:10Z)
• BILP-Q: Quantum Coalition Structure Generation [0.0]
  We propose BILP-Q, the first-ever general quantum approach for solving the Coalition Structure Generation problem (CSGP) We run BILP-Q on medium-size problems using a real quantum annealer (D-Wave)
  arXiv  Detail & Related papers  (2022-04-28T22:19:50Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• PBS-Calculus: A Graphical Language for Coherent Control of Quantum Computations [77.34726150561087]
  We introduce the PBS-calculus to represent and reason on quantum computations involving coherent control of quantum operations. We equip the language with an equational theory, which is proved to be sound and complete. We consider applications like the implementation of controlled permutations and the unrolling of loops.
  arXiv  Detail & Related papers  (2020-02-21T16:15:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.