Topological obstructions to quantum computation with unitary oracles

• URL: http://arxiv.org/abs/2011.10031v3
• Date: Thu, 28 Mar 2024 19:20:10 GMT
• Title: Topological obstructions to quantum computation with unitary oracles
• Authors: Zuzana Gavorová, Matan Seidel, Yonathan Touati,
• Abstract summary: Some tasks are impossible in quantum circuits, although their classical versions are easy, for example, cloning. We show limitations of process tomography, oracle neutralization, and $sqrt[dim U]U$, $UT$, and $Udagger$ algorithms. Our results strengthen an advantage of linear optics, challenge the experiments on relaxed causality, and motivate new algorithms with many-outcome measurements.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Algorithms with unitary oracles can be nested, which makes them extremely versatile. An example is the phase estimation algorithm used in many candidate algorithms for quantum speed-up. The search for new quantum algorithms benefits from understanding their limitations: Some tasks are impossible in quantum circuits, although their classical versions are easy, for example, cloning. An example with a unitary oracle $U$ is the if clause, the task to implement controlled $U$ (up to the phase on $U$). In classical computation the conditional statement is easy and essential. In quantum circuits the if clause was shown impossible from one query to $U$. Is it possible from polynomially many queries? Here we unify algorithms with a unitary oracle and develop a topological method to prove their limitations: No number of queries to $U$ and $U^\dagger$ lets quantum circuits implement the if clause, even if admitting approximations, postselection and relaxed causality. We also show limitations of process tomography, oracle neutralization, and $\sqrt[\dim U]{U}$, $U^T$, and $U^\dagger$ algorithms. Our results strengthen an advantage of linear optics, challenge the experiments on relaxed causality, and motivate new algorithms with many-outcome measurements.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Quantum State Learning Implies Circuit Lower Bounds [2.2667044928324747]
  We establish connections between state tomography, pseudorandomness, quantum state, circuit lower bounds. We show that even slightly non-trivial quantum state tomography algorithms would lead to new statements about quantum state synthesis.
  arXiv  Detail & Related papers  (2024-05-16T16:46:27Z)
• A one-query lower bound for unitary synthesis and breaking quantum cryptography [7.705803563459633]
  The Unitary Synthesis Problem asks whether any $n$qubit unitary $U$ can be implemented by an efficient quantum $A$ augmented with an oracle that computes an arbitrary Boolean function $f$. In this work, we prove unitary synthesis as an efficient challenger-ad game, which enables proving lower bounds by analyzing the maximum success probability of an adversary $Af$.
  arXiv  Detail & Related papers  (2023-10-13T05:39:42Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  We present a time analogue quantum algorithm making a single query (in superposition) to a classical oracle. We prove that every $n$-qubit state can be constructed to within 0.01 error by an $On/n)$-size circuit over an appropriate finite gate set.
  arXiv  Detail & Related papers  (2023-06-02T17:49:35Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
  arXiv  Detail & Related papers  (2023-01-05T11:05:22Z)
• 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)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• 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)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
  arXiv  Detail & Related papers  (2022-02-10T18:59:52Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• Quantum $k$-nearest neighbors algorithm [0.0]
  We present a quantum analog of classical $k$NN $-$ quantum $k$NN (Q$k$NN) $-$ based on fidelity as the similarity measure. Unlike classical $k$NN and existing quantum $k$NN algorithms, the proposed algorithm can be directly used on quantum data.
  arXiv  Detail & Related papers  (2020-03-20T10:48:57Z)

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.