One Clean Qubit Suffices for Quantum Communication Advantage
- URL: http://arxiv.org/abs/2310.02406v1
- Date: Tue, 3 Oct 2023 19:58:08 GMT
- Title: One Clean Qubit Suffices for Quantum Communication Advantage
- Authors: Srinivasan Arunachalam, Uma Girish and Noam Lifshitz
- Abstract summary: We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed.
Our proof is based on a recent hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and Minzer.
- Score: 3.729242965449096
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the one-clean-qubit model of quantum communication where one qubit
is in a pure state and all other qubits are maximally mixed. We demonstrate a
partial function that has a quantum protocol of cost $O(\log N)$ in this model,
however, every interactive randomized protocol has cost $\Omega(\sqrt{N})$,
settling a conjecture of Klauck and Lim. In contrast, all prior quantum versus
classical communication separations required at least $\Omega(\log N)$ clean
qubits. The function demonstrating our separation also has an efficient
protocol in the quantum-simultaneous-with-entanglement model of cost $O(\log N
)$. We thus recover the state-of-the-art separations between quantum and
classical communication complexity. Our proof is based on a recent
hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and
Minzer, in conjunction with tools from the representation theory of compact Lie
groups.
Related papers
- General Communication Enhancement via the Quantum Switch [15.779145740528417]
We conjecture that $mathcalP_n>0$ is both a necessary and sufficient condition for communication enhancement via the quantum $tt SWITCH$.
We then formulate a communication protocol involving the quantum $tt SWITCH$ which enhances the private capacity of the BB84 channel.
arXiv Detail & Related papers (2024-07-03T00:47:13Z) - Linear gate bounds against natural functions for position-verification [0.0]
A quantum position-verification scheme attempts to verify the spatial location of a prover.
We consider two well-studied position-verification schemes known as $f$-routing and $f$-BB84.
arXiv Detail & Related papers (2024-02-28T19:00:10Z) - Trade-offs between Entanglement and Communication [5.88864611435337]
We show that quantum simultaneous protocols with $tildeTheta(k5 log3 n)$ qubits of entanglement can exponentially outperform two-way randomized protocols with $O(k)$ qubits of entanglement.
Prior to our work, only a relational separation was known.
arXiv Detail & Related papers (2023-06-02T01:49:39Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods.
We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
arXiv Detail & Related papers (2023-03-03T18:23:20Z) - Quantum teleportation in the commuting operator framework [63.69764116066747]
We present unbiased teleportation schemes for relative commutants $N'cap M$ of a large class of finite-index inclusions $Nsubseteq M$ of tracial von Neumann algebras.
We show that any tight teleportation scheme for $N$ necessarily arises from an orthonormal unitary Pimsner-Popa basis of $M_n(mathbbC)$ over $N'$.
arXiv Detail & Related papers (2022-08-02T00:20:46Z) - A direct product theorem for quantum communication complexity with
applications to device-independent cryptography [6.891238879512672]
We show that for a distribution $p$ that is product across the input sets of the $l$ players, the success probability of any entanglement-assisted quantum communication protocol goes down exponentially in $n$.
We also show that it is possible to do device-independent (DI) quantum cryptography without the assumption that devices do not leak any information.
arXiv Detail & Related papers (2021-06-08T12:52:10Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
Two players each receive $t$ samples from one distribution over $[n]$.
The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart.
We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
arXiv Detail & Related papers (2020-06-26T09:05:58Z) - Secure multi-party quantum computation with few qubits [0.0]
We consider the task of secure multi-party distributed quantum computation on a quantum network.
We propose a protocol based on quantum error correction which reduces the number of necessary qubits.
We showcase our protocol on a small example for a 7-node network.
arXiv Detail & Related papers (2020-04-22T10:48:30Z) - 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 Coupon Collector [62.58209964224025]
We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements.
We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
arXiv Detail & Related papers (2020-02-18T16:14:55Z) - Communication Cost of Quantum Processes [49.281159740373326]
A common scenario in distributed computing involves a client who asks a server to perform a computation on a remote computer.
An important problem is to determine the minimum amount of communication needed to specify the desired computation.
We analyze the total amount of (classical and quantum) communication needed by a server in order to accurately execute a quantum process chosen by a client.
arXiv Detail & Related papers (2020-02-17T08:51:42Z)
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.