Lower Bounds for Unitary Property Testing with Proofs and Advice

• URL: http://arxiv.org/abs/2401.07912v2
• Date: Thu, 13 Jun 2024 09:55:24 GMT
• Title: Lower Bounds for Unitary Property Testing with Proofs and Advice
• Authors: Jordi Weggemans,
• Abstract summary: We propose a new technique for proving lower bounds on the quantum query of unitary property testing. All obtained lower bounds hold for any $mathsfC$-tester with $mathsfC subseteq mathsfQMA(2)/mathsfqpoly$. We show that there exist quantum oracles relative to which $mathsfQMA(2) notsupset mathsfSBQP$ and $mathsfQMA/mathsfqpoly
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In unitary property testing a quantum algorithm, also known as a tester, is given query access to a black-box unitary and has to decide whether it satisfies some property. We propose a new technique for proving lower bounds on the quantum query complexity of unitary property testing and related problems, which utilises its connection to unitary channel discrimination. The main advantage of this technique is that all obtained lower bounds hold for any $\mathsf{C}$-tester with $\mathsf{C} \subseteq \mathsf{QMA}(2)/\mathsf{qpoly}$, showing that even having access to both (unentangled) quantum proofs and advice does not help for many unitary problems. We apply our technique to prove lower bounds for problems like quantum phase estimation, the entanglement entropy problem, quantum Gibbs sampling and more, removing all logarithmic factors in the lower bounds obtained by the sample-to-query lifting theorem of Wang and Zhang (2023). As a direct corollary, we show that there exist quantum oracles relative to which $\mathsf{QMA}(2) \not\supset \mathsf{SBQP}$ and $\mathsf{QMA}/\mathsf{qpoly} \not\supset \mathsf{SBQP}$. The former shows that, at least in a black-box way, having unentangled quantum proofs does not help in solving problems that require high precision.

Related papers

• Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
  We generalize quantum-classical PCPs to allow for $q$ quantum queries to a classical proof. Surprisingly, this shows that we can amplify the promise gap from inverse to constant for constant query quantum-classicals. Even though we can achieve promise gap, our result also gives strong evidence that there exists no constant query quantum-classical PCP for $mathsfQCMA$.
  arXiv  Detail & Related papers  (2024-11-01T18:00:56Z)
• 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 Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds [1.3927943269211591]
  This work studies three quantum-verifier based generalizations of $mathsfPH$. We first resolve several open problems from [GSSSY22], including a collapse theorem and a Karp-Lipton theorem for $mathsfQCPH$. We show one-sided error reduction for $mathsfpureQPH$, as well as the first bounds relating these quantum variants of $mathsfPH$.
  arXiv  Detail & Related papers  (2024-01-03T09:12:25Z)
• Quantum Lower Bounds by Sample-to-Query Lifting [7.319050391449301]
  We propose an arguably new method for proving quantum query lower bounds by a quantum sample-to-query lifting theorem. We provide unified proof for some known lower bounds, including those for phase/amplitude estimation and Hamiltonian simulation.
  arXiv  Detail & Related papers  (2023-08-03T14:41:49Z)
• 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)
• Unitary property testing lower bounds by polynomials [0.15229257192293197]
  We study unitary property testing, where a quantum algorithm is given query access to a black-box unitary. Characterizing the complexity of these problems requires new algorithmic techniques and lower bound methods. We present a unitary property testing-based approach towards an oracle separation between $mathsfQMA$ and $mathsfQMA(2)$.
  arXiv  Detail & Related papers  (2022-10-12T03:01:00Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Quantum Proofs of Proximity [6.160793572747927]
  We show that QMA proofs of proximity can be exponentially stronger than classical proofs of proximity and quantum testers. Our results include an algorithmic framework that enables quantum speedups for testing an expressive class of properties. We also propose a QMA algorithm for testing graph bipartitneness, a property that lies outside of this family.
  arXiv  Detail & Related papers  (2021-05-08T13:15:30Z)

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.