Exponential separation in quantum query complexity of the quantum switch with respect to simulations with standard quantum circuits

• URL: http://arxiv.org/abs/2409.18420v2
• Date: Tue, 1 Oct 2024 17:46:25 GMT
• Title: Exponential separation in quantum query complexity of the quantum switch with respect to simulations with standard quantum circuits
• Authors: Hlér Kristjánsson, Tatsuki Odake, Satoshi Yoshida, Philip Taranto, Jessica Bavaresco, Marco Túlio Quintino, Mio Murao,
• Abstract summary: We prove that the action of the quantum switch on two $n$-qubit quantum channels cannot be simulated deterministically. This demonstrates an exponential separation in quantum query complexity of indefinite causal order compared to standard quantum circuits.
• Score: 1.151731504874944
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Quantum theory is consistent with a computational model permitting black-box operations to be applied in an indefinite causal order, going beyond the standard circuit model of computation. The quantum switch -- the simplest such example -- has been shown to provide numerous information-processing advantages. Here, we prove that the action of the quantum switch on two $n$-qubit quantum channels cannot be simulated deterministically and exactly by any causally ordered quantum circuit that uses $M$ calls to one channel and one call to the other, if $M \leq \max(2, 2^n-1)$. This demonstrates an exponential separation in quantum query complexity of indefinite causal order compared to standard quantum circuits.

Related papers

• Can the quantum switch be deterministically simulated? [1.151731504874944]
  We show that when only one extra call of each input channel is available, the quantum switch cannot be simulated by any quantum circuit. This result stands in stark contrast with the known fact that, when the quantum switch acts exclusively on unitary channels, its action can be simulated.
  arXiv  Detail & Related papers  (2024-09-26T18:34:14Z)
• Lightcone Bounds for Quantum Circuit Mapping via Uncomplexity [1.0360348400670518]
  We show that a minimal SWAP-gate count for executing a quantum circuit on a device emerges via the minimization of the distance between quantum states. This work constitutes the first use of quantum circuit uncomplexity to practically-relevant quantum computing.
  arXiv  Detail & Related papers  (2024-02-01T10:32:05Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Quantum Query Complexity of Boolean Functions under Indefinite Causal Order [0.9208007322096533]
  We study the query complexity of Boolean functions under general higher order quantum computations. We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity. We find some functions for which the minimum error with which they can be computed using two queries is strictly lower when exploiting causally indefinite supermaps.
  arXiv  Detail & Related papers  (2023-07-18T13:12:55Z)
• Quantum process tomography of continuous-variable gates using coherent states [49.299443295581064]
  We demonstrate the use of coherent-state quantum process tomography (csQPT) for a bosonic-mode superconducting circuit. We show results for this method by characterizing a logical quantum gate constructed using displacement and SNAP operations on an encoded qubit.
  arXiv  Detail & Related papers  (2023-03-02T18:08:08Z)
• Quantum communication complexity of linear regression [0.05076419064097732]
  We show that quantum computers have provable and exponential speedups in terms of communication for some fundamental linear algebra problems. We propose an efficient quantum protocol for quantum singular value transformation.
  arXiv  Detail & Related papers  (2022-10-04T13:27:01Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• 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)
• Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
  We experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor. We show that while operator spreading is captured by an efficient classical model, operator entanglement requires exponentially scaled computational resources to simulate.
  arXiv  Detail & Related papers  (2021-01-21T22:18:49Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)
• Computational advantage from quantum superposition of multiple temporal orders of photonic gates [0.0]
  A control quantum system can coherently determine the order in which a target quantum system undergoes $N$ gate operations. We experimentally demonstrate the quantum $N$-switch with $N=4$ gates acting on a photonic-polarization qubit. This is the first observation of a quantum superposition of more than $N=2$ temporal orders.
  arXiv  Detail & Related papers  (2020-02-18T19:00:01Z)

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.