Approximate traces on groups and the quantum complexity class $\operatorname{MIP}^{co,s}$

• URL: http://arxiv.org/abs/2209.08009v1
• Date: Fri, 16 Sep 2022 15:45:49 GMT
• Title: Approximate traces on groups and the quantum complexity class $\operatorname{MIP}^{co,s}$
• Authors: Isaac Goldbring and Bradd Hart
• Abstract summary: We introduce the notion of a qc-modulus, which encodes approximations to quantum commuting correlations. We show that the existence of a computable qc-modulus gives a negative answer to a natural variant of the aforementioned question.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: An open question in quantum complexity theory is whether or not the class $\operatorname{MIP}^{co}$, consisting of languages that can be efficiently verified using interacting provers sharing quantum resources according to the quantum commuting model, coincides with the class $coRE$ of languages with recursively enumerable complement. We introduce the notion of a qc-modulus, which encodes approximations to quantum commuting correlations, and show that the existence of a computable qc-modulus gives a negative answer to a natural variant of the aforementioned question.

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)
• 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)
• Quantum Algorithms for Compositional Text Processing [1.3654846342364308]
  We focus on the recently proposed DisCoCirc framework for natural language, and propose a quantum adaptation, QDisCoCirc. This is motivated by a compositional approach to rendering AI interpretable. For the model-native primitive operation of text similarity, we derive quantum algorithms for fault-tolerant quantum computers.
  arXiv  Detail & Related papers  (2024-08-12T11:21:40Z)
• The Power of Lorentz Quantum Computer [6.9754404995027794]
  We demonstrate the superior capabilities of the recently proposed Lorentz quantum computer (LQC) compared to conventional quantum computers. We introduce an associated computational complexity class $text Psharp textP$, demonstrating its equivalence to the complexity class $text Psharp textP$. We show that the quantum computing with postselection proposed by Aaronson can be efficiently simulated by LQC, but not vice versa.
  arXiv  Detail & Related papers  (2024-03-07T03:00:09Z)
• 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)
• Towards Quantum Computational Mechanics [1.530480694206666]
  We show how quantum computing can be used to solve representative element volume (RVE) problems in computational homogenisation. Our quantum RVE solver attains exponential acceleration with respect to classical solvers.
  arXiv  Detail & Related papers  (2023-12-06T12:53:02Z)
• Semantic embedding for quantum algorithms [0.0]
  A need has developed for an assurance of the correctness of high-level quantum algorithmic reasoning. Many quantum algorithms have been unified and improved using quantum signal processing (QSP) and quantum singular value transformation (QSVT) We show that QSP/QSVT can be treated and combined modularly, purely in terms of the functional transforms they embed. We also identify existing quantum algorithms whose use of semantic embedding is implicit, spanning from distributed search to soundness in quantum cryptography.
  arXiv  Detail & Related papers  (2023-04-27T17:55:40Z)
• 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)
• Facial Expression Recognition on a Quantum Computer [68.8204255655161]
  We show a possible solution to facial expression recognition using a quantum machine learning approach. We define a quantum circuit that manipulates the graphs adjacency matrices encoded into the amplitudes of some appropriately defined quantum states.
  arXiv  Detail & Related papers  (2021-02-09T13:48:00Z)
• A MLIR Dialect for Quantum Assembly Languages [78.8942067357231]
  We demonstrate the utility of the Multi-Level Intermediate Representation (MLIR) for quantum computing. We extend MLIR with a new quantum dialect that enables the expression and compilation of common quantum assembly languages. We leverage a qcor-enabled implementation of the QIR quantum runtime API to enable a retargetable (quantum hardware agnostic) compiler workflow.
  arXiv  Detail & Related papers  (2021-01-27T13:00:39Z)
• Extending C++ for Heterogeneous Quantum-Classical Computing [56.782064931823015]
  qcor is a language extension to C++ and compiler implementation that enables heterogeneous quantum-classical programming, compilation, and execution in a single-source context. Our work provides a first-of-its-kind C++ compiler enabling high-level quantum kernel (function) expression in a quantum-language manner.
  arXiv  Detail & Related papers  (2020-10-08T12:49:07Z)

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.