Oracle separations of hybrid quantum-classical circuits

• URL: http://arxiv.org/abs/2201.01904v1
• Date: Thu, 6 Jan 2022 03:10:53 GMT
• Title: Oracle separations of hybrid quantum-classical circuits
• Authors: Atul Singh Arora, Alexandru Gheorghiu, Uttam Singh
• Abstract summary: 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.
• Score: 68.96380145211093
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: An important theoretical problem in the study of quantum computation, that is also practically relevant in the context of near-term quantum devices, is to understand the computational power of hybrid models, that combine poly-time classical computation with short-depth quantum computation. Here, we consider two such models: CQ_d which captures the scenario of a polynomial-time classical algorithm that queries a d-depth quantum computer many times; and QC_d which is more analogous to measurement-based quantum computation and captures the scenario of a d-depth quantum computer with the ability to change the sequence of gates being applied depending on measurement outcomes processed by a classical computation. Chia, Chung & Lai (STOC 2020) and Coudron & Menda (STOC 2020) showed that these models (with d=log^O(1) (n)) are strictly weaker than BQP (the class of problems solvable by poly-time quantum computation), relative to an oracle, disproving a conjecture of Jozsa in the relativised world. We show that, despite the similarities between CQ_d and QC_d, the two models are incomparable, i.e. CQ_d $\nsubseteq$ QC_d and QC_d $\nsubseteq$ CQ_d relative to an oracle. In other words, there exist problems that one model can solve but not the other and vice versa. We do this by considering new oracle problems that capture the distinctions between the two models and by introducing the notion of an intrinsically stochastic oracle, an oracle whose responses are inherently randomised, which is used for our second result. While we leave showing the second separation relative to a standard oracle as an open problem, we believe the notion of stochastic oracles could be of independent interest for studying complexity classes which have resisted separation in the standard oracle model. Our constructions also yield simpler oracle separations between the hybrid models and BQP, compared to earlier works.

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)
• Quantum Circuit Learning on NISQ Hardware [0.0]
  Current quantum computers are small and error-prone systems. Fault-tolerant quantum computers are not expected to be available in the near future. We show that exemplary QCL circuits with up to three qubits are executable on the IBM quantum computer.
  arXiv  Detail & Related papers  (2024-05-03T13:00: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)
• SQL2Circuits: Estimating Metrics for SQL Queries with a Quantum Natural Language Processing Method [1.5540058359482858]
  This work employs a quantum natural language processing (QNLP)-inspired approach for constructing a quantum machine learning model. The model consists of an encoding mechanism and a training phase, including classical and quantum subroutines. We conclude that our model reaches an accuracy equivalent to that of the QNLP model in the binary classification tasks.
  arXiv  Detail & Related papers  (2023-06-14T14:23:19Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• 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)
• Hybrid Quantum Classical Simulations [0.0]
  We report on two major hybrid applications of quantum computing, namely, the quantum approximate optimisation algorithm (QAOA) and the variational quantum eigensolver (VQE) Both are hybrid quantum classical algorithms as they require incremental communication between a classical central processing unit and a quantum processing unit to solve a problem.
  arXiv  Detail & Related papers  (2022-10-06T10:49:15Z)
• On the Super-exponential Quantum Speedup of Equivariant Quantum Machine Learning Algorithms with SU($d$) Symmetry [14.281289319738633]
  We enhance a natural model of quantum computation--permutational quantum computing (PQC)--and defines a more powerful model: PQC+. While PQC was shown to be effectively classically simulatable, we exhibit a problem which can be efficiently solved on PQC+ machine. We discuss practical quantum machine learning algorithms which can be carried out in the paradigm of PQC+.
  arXiv  Detail & Related papers  (2022-07-15T01:41:53Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Computational power of one- and two-dimensional dual-unitary quantum circuits [0.6946929968559495]
  Quantum circuits that are classically simulatable tell us when quantum computation becomes less powerful than or equivalent to classical computation. We make use of dual-unitary quantum circuits (DUQCs), which have been recently investigated as exactly solvable models of non-equilibrium physics.
  arXiv  Detail & Related papers  (2021-03-16T17:37:11Z)

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.