Revisiting BQP with Non-Collapsing Measurements

• URL: http://arxiv.org/abs/2411.04085v1
• Date: Wed, 06 Nov 2024 18:06:10 GMT
• Title: Revisiting BQP with Non-Collapsing Measurements
• Authors: David Miloschewsky, Supartha Podder,
• Abstract summary: We show that when equipped with the ability to perform non-collapsing measurements, BQP contains both BQP and SZK. By formulating an alternative equivalent model of PDQP, we prove the positive weighted adversary method. We also explore related settings, obtaining tight bounds in BQP with the ability to copy arbitrary states.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The study of non-collapsing measurements was initiated by Aaronson, Bouland, Fitzsimons, and Lee, who showed that BQP, when equipped with the ability to perform non-collapsing measurements (denoted as PDQP), contains both BQP and SZK, yet still requires $\Omega (N^{1/4})$ queries to find an element in an unsorted list. By formulating an alternative equivalent model of PDQP, we prove the positive weighted adversary method, obtaining a variety of new lower bounds and establishing a trade-off between queries and non-collapsing measurements. The method allows us to examine the well-studied majority and element distinctness problems, while also tightening the bound for the search problem to $\Theta (N^{1/3})$. Additionally, we explore related settings, obtaining tight bounds in BQP with the ability to copy arbitrary states (called CBQP) and PDQP with non-adaptive queries.

Related papers

• The benefits of query-based KGQA systems for complex and temporal questions in LLM era [55.20230501807337]
  Large language models excel in question-answering (QA) yet still struggle with multi-hop reasoning and temporal questions.<n> Query-based knowledge graph QA (KGQA) offers a modular alternative by generating executable queries instead of direct answers.<n>We explore multi-stage query-based framework for WikiData QA, proposing multi-stage approach that enhances performance on challenging multi-hop and temporal benchmarks.
  arXiv  Detail & Related papers  (2025-07-16T06:41:03Z)
• On additive error approximations to #BQP [0.34089646689382486]
  We study additive approximations to a quantum generalization of counting classes known as #BQP. First, we show that there exist efficient quantum algorithms that achieve additive approximations to #BQP problems to an error exponential in the number of witness qubits in the corresponding verifier circuit.
  arXiv  Detail & Related papers  (2024-11-04T20:51:20Z)
• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  Variational quantum algorithms have become the de facto model for current quantum computations. One such problem is unstructured search which consists on finding a particular bit of string. We trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity.
  arXiv  Detail & Related papers  (2024-03-22T18:00:03Z)
• SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions [50.20087216230159]
  We study the complexity of Non-Gaussian Component Analysis (NGCA) in the Statistical Query model. We prove near-optimal SQ lower bounds for NGCA under the moment-matching condition only.
  arXiv  Detail & Related papers  (2024-03-07T18:49:32Z)
• The Power of Adaptivity in Quantum Query Algorithms [0.5702169790677977]
  We study the depth-computation trade-off in the query model, where the depth corresponds to the number of adaptive query rounds and the number of parallel queries per round. We achieve the strongest known separation between quantum algorithms with $r$ versus $r-1$ rounds of adaptivity.
  arXiv  Detail & Related papers  (2023-11-27T18:21:32Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  We take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle. We introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries.
  arXiv  Detail & Related papers  (2023-10-26T18:23:21Z)
• Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
  AQCs allow to implement problems of research interest, which has sparked the development of quantum representations for computer vision tasks. In this work, we explore the potential of using this information for probabilistic balanced k-means clustering. Instead of discarding non-optimal solutions, we propose to use them to compute calibrated posterior probabilities with little additional compute cost. This allows us to identify ambiguous solutions and data points, which we demonstrate on a D-Wave AQC on synthetic tasks and real visual data.
  arXiv  Detail & Related papers  (2023-10-18T17:59:45Z)
• A Generalized Quantum Branching Program [0.5584060970507505]
  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.
  arXiv  Detail & Related papers  (2023-07-21T07:27:51Z)
• PACIFIC: Towards Proactive Conversational Question Answering over Tabular and Textual Data in Finance [96.06505049126345]
  We present a new dataset, named PACIFIC. Compared with existing CQA datasets, PACIFIC exhibits three key features: (i) proactivity, (ii) numerical reasoning, and (iii) hybrid context of tables and text. A new task is defined accordingly to study Proactive Conversational Question Answering (PCQA), which combines clarification question generation and CQA. UniPCQA performs multi-task learning over all sub-tasks in PCQA and incorporates a simple ensemble strategy to alleviate the error propagation issue in the multi-task learning by cross-validating top-$k$ sampled Seq2Seq
  arXiv  Detail & Related papers  (2022-10-17T08:06:56Z)
• 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)
• Towards Clear Expectations for Uncertainty Estimation [64.20262246029286]
  Uncertainty Quantification (UQ) is crucial to achieve trustworthy Machine Learning (ML) Most UQ methods suffer from disparate and inconsistent evaluation protocols. This opinion paper offers a new perspective by specifying those requirements through five downstream tasks.
  arXiv  Detail & Related papers  (2022-07-27T07:50:57Z)
• Variational learning algorithms for quantum query complexity [3.980076328494117]
  We develop variational learning algorithms to study quantum query complexity. We apply our method to analyze various cases of quantum query complexity. Our method can be readily implemented on the near-term Noisy Intermediate-Scale Quantum (NISQ) devices.
  arXiv  Detail & Related papers  (2022-05-16T05:16:15Z)
• 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)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Geometry of Banach spaces: a new route towards Position Based Cryptography [65.51757376525798]
  We study Position Based Quantum Cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol. We show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol.
  arXiv  Detail & Related papers  (2021-03-30T13:55:11Z)
• PAQ: 65 Million Probably-Asked Questions and What You Can Do With Them [70.09741980324912]
  Open-domain Question Answering models which directly leverage question-answer (QA) pairs show promise in terms of speed and memory. We introduce a new QA-pair retriever, RePAQ, to complement PAQ. We find that PAQ preempts and caches test questions, enabling RePAQ to match the accuracy of recent retrieve-and-read models.
  arXiv  Detail & Related papers  (2021-02-13T23:43:45Z)
• The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs [10.042878093985458]
  Ontology-mediated querying and querying in the presence of constraints are two key database problems. We study the limits of efficient query evaluation in the context of guarded and frontier-guarded TGDs and on UCQs as the actual queries.
  arXiv  Detail & Related papers  (2019-12-28T11:08:33Z)

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.