Open Problems Related to Quantum Query Complexity

• URL: http://arxiv.org/abs/2109.06917v1
• Date: Tue, 14 Sep 2021 18:36:15 GMT
• Title: Open Problems Related to Quantum Query Complexity
• Authors: Scott Aaronson
• Abstract summary: I offer a case that quantum query complexity still has loads of enticing and fundamental open problems. I offer a case that quantum query complexity still has loads of enticing and fundamental open problems.
• Score: 4.467248776406005
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: I offer a case that quantum query complexity still has loads of enticing and fundamental open problems -- from relativized QMA versus QCMA and BQP versus IP, to time/space tradeoffs for collision and element distinctness, to polynomial degree versus quantum query complexity for partial functions, to the Unitary Synthesis Problem and more.

Related papers

• Complexity Theory for Quantum Promise Problems [5.049812996253858]
  We study the relationship between quantum cryptography and complexity theory, especially within Impagliazzo's five worlds framework. We focus on complexity classes p/mBQP, p/mQ(C)MA, $mathrmp/mQSZK_hv$, p/mQIP, and p/mPSPACE, where "p/mC" denotes classes with pure (p) or mixed (m) states. We apply this framework to cryptography, showing that breaking one-way state generators, pseudorandom states, and EFI is bounded by mQCMA or
  arXiv  Detail & Related papers  (2024-11-06T07:29:52Z)
• On the quantum time complexity of divide and conquer [42.7410400783548]
  We study the time complexity of quantum divide and conquer algorithms for classical problems. We apply these theorems to an array of problems involving strings, integers, and geometric objects.
  arXiv  Detail & Related papers  (2023-11-28T01:06:03Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more [5.69353915790503]
  There are problems for which there is no trivial' computational advantage possible with the current quantum hardware. We would like to have evidence that it is difficult to solve those problems on quantum computers; but what is their exact complexity? By the use of the QSETH framework [Buhrman-Patro-Speelman 2021], we are able to understand the quantum complexity of a few natural variants of CNFSAT.
  arXiv  Detail & Related papers  (2023-09-28T13:30:20Z)
• Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines [0.9374652839580183]
  This work presents a study of Kolmogorov complexity for general quantum states from the perspective of deterministic-control quantum Turing Machines (dcq-TM) We extend the dcq-TM model to incorporate mixed state inputs and outputs, and define dcq-computable states as those that can be approximated by a dcq-TM.
  arXiv  Detail & Related papers  (2023-05-23T17:07:58Z)
• Quantum Parameterized Complexity [1.01129133945787]
  We introduce the quantum analogues of a range of parameterized complexity classes. This framework exposes a rich classification of the complexity of parameterized versions of QMA-hard problems.
  arXiv  Detail & Related papers  (2022-03-15T15:34:38Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)

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.