Complexity Theory for Quantum Promise Problems

• URL: http://arxiv.org/abs/2411.03716v1
• Date: Wed, 06 Nov 2024 07:29:52 GMT
• Title: Complexity Theory for Quantum Promise Problems
• Authors: Nai-Hui Chia, Kai-Min Chung, Tzu-Hsiang Huang, Jhih-Wei Shih,
• Abstract summary: 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
• Score: 5.049812996253858
• License:
• Abstract: Quantum computing introduces many problems rooted in physics, asking to compute information from input quantum states. Determining the complexity of these problems has implications for both computer science and physics. However, as existing complexity theory primarily addresses problems with classical inputs and outputs, it lacks the framework to fully capture the complexity of quantum-input problems. This gap is relevant when studying the relationship between quantum cryptography and complexity theory, especially within Impagliazzo's five worlds framework, as characterizing the security of quantum cryptographic primitives requires complexity classes for problems involving quantum inputs. To bridge this gap, we examine the complexity theory of quantum promise problems, which determine if input quantum states have certain properties. We focus on complexity classes p/mBQP, p/mQ(C)MA, $\mathrm{p/mQSZK_{hv}}$, p/mQIP, and p/mPSPACE, where "p/mC" denotes classes with pure (p) or mixed (m) states corresponding to any classical class C. We establish structural results, including complete problems, search-to-decision reductions, and relationships between classes. Notably, our findings reveal differences from classical counterparts, such as p/mQIP $\neq$ p/mPSPACE and $\mathrm{mcoQSZK_{hv}} \neq \mathrm{mQSZK_{hv}}$. As an application, we apply this framework to cryptography, showing that breaking one-way state generators, pseudorandom states, and EFI is bounded by mQCMA or $\mathrm{mQSZK_{hv}}$. We also show that the average-case hardness of $\mathrm{pQCZK_{hv}}$ implies the existence of EFI. These results provide new insights into Impagliazzo's worlds, establishing a connection between quantum cryptography and quantum promise complexity theory. We also extend our findings to quantum property testing and unitary synthesis, highlighting further applications of this new framework.

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• 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 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)
• QNEAT: Natural Evolution of Variational Quantum Circuit Architecture [95.29334926638462]
  We focus on variational quantum circuits (VQC), which emerged as the most promising candidates for the quantum counterpart of neural networks. Although showing promising results, VQCs can be hard to train because of different issues, e.g., barren plateau, periodicity of the weights, or choice of architecture. We propose a gradient-free algorithm inspired by natural evolution to optimize both the weights and the architecture of the VQC.
  arXiv  Detail & Related papers  (2023-04-14T08:03:20Z)
• Quantum Merlin-Arthur proof systems for synthesizing quantum states [0.0]
  We investigate a state synthesizing counterpart of the class NP-synthesizing. We establish that the family of UQMA witnesses, considered as one of the most natural candidates, is in stateQMA. We demonstrate that stateQCMA achieves perfect completeness.
  arXiv  Detail & Related papers  (2023-03-03T12:14: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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• 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 Computational Complexity -- From Quantum Information to Black Holes and Back [0.0]
  Quantum computational complexity was suggested as a new entry in the holographic dictionary. We show how it can be used to define complexity for generic quantum systems. We highlight the relation between complexity, chaos and scrambling in chaotic systems.
  arXiv  Detail & Related papers  (2021-10-27T18:00:12Z)
• Quantum Meets the Minimum Circuit Size Problem [3.199102917243584]
  We study the Minimum Circuit Size Problem (MCSP) in the quantum setting. MCSP is a problem to compute the circuit complexity of Boolean functions. We show that these problems are not trivially in NP but in QCMA (or have QCMA protocols)
  arXiv  Detail & Related papers  (2021-08-06T15:34:49Z)

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.