Quantum advantage for computations with limited space

• URL: http://arxiv.org/abs/2008.06478v2
• Date: Fri, 18 Dec 2020 21:29:37 GMT
• Title: Quantum advantage for computations with limited space
• Authors: Dmitri Maslov, Jin-Sung Kim, Sergey Bravyi, Theodore J. Yoder, and Sarah Sheldon
• Abstract summary: We consider space-restricted computations, where input is a read-only memory and only one (qu)bit can be computed on. We experimentally demonstrate computations of $3$-, $4$-, $5$-, and $6$- by quantum circuits, leveraging custom two-qubit gates.
• Score: 6.327095331866255
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum computations promise the ability to solve problems intractable in the classical setting. Restricting the types of computations considered often allows to establish a provable theoretical advantage by quantum computations, and later demonstrate it experimentally. In this paper, we consider space-restricted computations, where input is a read-only memory and only one (qu)bit can be computed on. We show that $n$-bit symmetric Boolean functions can be implemented exactly through the use of quantum signal processing as restricted space quantum computations using $O(n^2)$ gates, but some of them may only be evaluated with probability $1/2 + O(n/\sqrt{2}^n)$ by analogously defined classical computations. We experimentally demonstrate computations of $3$-, $4$-, $5$-, and $6$-bit symmetric Boolean functions by quantum circuits, leveraging custom two-qubit gates, with algorithmic success probability exceeding the best possible classically. This establishes and experimentally verifies a different kind of quantum advantage -- one where quantum scrap space is more valuable than analogous classical space -- and calls for an in-depth exploration of space-time tradeoffs in quantum circuits.

Related papers

• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Simulation of quantum algorithms using classical probabilistic bits and circuits [0.0]
  We discuss a new approach to simulate quantum algorithms using classical probabilistic bits and circuits. Key idea in this mapping is to store both the amplitude and phase information of the complex coefficients that describe the qubit state in the probabilities. We show how to implement the analogs of single-qubit and two-qubit gates in the probability space using correlation-inducing operations.
  arXiv  Detail & Related papers  (2023-07-26T18:49:42Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Post-Quantum Zero-Knowledge with Space-Bounded Simulation [8.69082943773532]
  We introduce a fine-grained notion of post-quantum zero-knowledge that is more compatible with near-term quantum devices. For verifiers with logarithmic quantum space $s$ and classical space, we show that $(s,f)$-space-bounded QZK, for $f(s)=2s$, can be achieved. For verifiers with superlogarithmic quantum space $s$, assuming existence of post-quantum one-way, we show that $(s,f)$-space-bounded QZK protocols, with fully black
  arXiv  Detail & Related papers  (2022-10-12T11:13:56Z)
• 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)
• Universal Statistical Simulator [0.0]
  We present a quantum computer code for a Galton Board Simulator that is exponentially faster than a classical calculation. We demonstrate a straight forward implementation on a quantum computer, using only three types of quantum gate, which calculates $2n$ trajectories using $mathcalO (n2)$ resources.
  arXiv  Detail & Related papers  (2022-02-03T17:55:58Z)
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications [10.436969366019015]
  We show that any $Theta(n)$-depth circuit can be prepared with a $Theta(log(nd)) with $O(ndlog d)$ ancillary qubits. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories.
  arXiv  Detail & Related papers  (2022-01-27T13:16:30Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Quantum Logspace Algorithm for Powering Matrices with Bounded Norm [7.510385608531827]
  We give a quantum logspace algorithm for powering contraction matrices, that is, with spectral norm at most1. The algorithm applies only unitary operators, without intermediate measurements. This shows that the deferred-measurement principle, a fundamental principle of quantum computing, applies also for quantum logspace algorithms.
  arXiv  Detail & Related papers  (2020-06-08T19:01:04Z)
• 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)

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.