Quantum randomized encoding, verification of quantum computing,
no-cloning, and blind quantum computing
- URL: http://arxiv.org/abs/2011.03141v2
- Date: Thu, 4 Nov 2021 03:16:18 GMT
- Title: Quantum randomized encoding, verification of quantum computing,
no-cloning, and blind quantum computing
- Authors: Tomoyuki Morimae
- Abstract summary: We show that if quantum randomized encoding of BB84 state generations is possible with an encoding operation $E$, a two-round verification of quantum computing is possible with a classical verifier.
We show that too good quantum randomized encoding with a classical encoding operation is impossible.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Randomized encoding is a powerful cryptographic primitive with various
applications such as secure multiparty computation, verifiable computation,
parallel cryptography, and complexity lower-bounds. Intuitively, randomized
encoding $\hat{f}$ of a function $f$ is another function such that $f(x)$ can
be recovered from $\hat{f}(x)$, and nothing except for $f(x)$ is leaked from
$\hat{f}(x)$. Its quantum version, quantum randomized encoding, has been
introduced recently [Brakerski and Yuen, arXiv:2006.01085]. Intuitively,
quantum randomized encoding $\hat{F}$ of a quantum operation $F$ is another
quantum operation such that, for any quantum state $\rho$, $F(\rho)$ can be
recovered from $\hat{F}(\rho)$, and nothing except for $F(\rho)$ is leaked from
$\hat{F}(\rho)$. In this paper, we show that if quantum randomized encoding of
BB84 state generations is possible with an encoding operation $E$, then a
two-round verification of quantum computing is possible with a classical
verifier who can additionally do the operation $E$. One of the most important
goals in the field of the verification of quantum computing is to construct a
verification protocol with a verifier as classical as possible. This result
therefore demonstrates a potential application of quantum randomized encoding
to the verification of quantum computing: if we can find a good quantum
randomized encoding (in terms of the encoding complexity), then we can
construct a good verification protocol of quantum computing. We, however, also
show that too good quantum randomized encoding is impossible: if quantum
randomized encoding with a classical encoding operation is possible, then the
no-cloning is violated. We finally consider a natural modification of blind
quantum computing protocols in such a way that the server gets the output like
quantum randomized encoding. We show that the modified protocol is not secure.
Related papers
- A Cryptographic Perspective on the Verifiability of Quantum Advantage [5.857929080874288]
This paper investigates the verification of quantum advantage from a cryptographic perspective.
We establish a strong connection between the verifiability of quantum advantage and cryptographic and complexity primitives.
Our work shows that the quest for verifiable quantum advantages may lead to applications of quantum cryptography.
arXiv Detail & Related papers (2023-10-23T00:31:51Z) - 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) - 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) - Automatic quantum circuit encoding of a given arbitrary quantum state [0.0]
We propose a quantum-classical hybrid algorithm to encode a given arbitrarily quantum state onto an optimal quantum circuit.
The proposed algorithm employs as an objective function the absolute value of fidelity $F = langle 0 vert hatmathcalCdagger vert Psi rangle$.
We experimentally demonstrate that a quantum circuit generated by the AQCE algorithm can indeed represent the original quantum state reasonably on a noisy real quantum device.
arXiv Detail & Related papers (2021-12-29T12:33:41Z) - 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) - Quantum Algorithm for Fidelity Estimation [8.270684567157987]
For two unknown mixed quantum states $rho$ and $sigma$ in an $N$-dimensional space, computing their fidelity $F(rho,sigma)$ is a basic problem.
We propose a quantum algorithm that solves this problem in $namepoly(log (N), r, 1/varepsilon)$ time.
arXiv Detail & Related papers (2021-03-16T13:57:01Z) - Random access codes via quantum contextual redundancy [0.0]
We propose a protocol to encode classical bits in the measurement statistics of many-body Pauli observables.
We exploit by encoding the data into a set of convenient context eigenstates.
This allows to randomly access the encoded data with few resources.
arXiv Detail & Related papers (2021-03-01T18:50:46Z) - Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs"
We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM)
As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
arXiv Detail & Related papers (2020-09-29T08:41:53Z) - Fault-tolerant Coding for Quantum Communication [71.206200318454]
encode and decode circuits to reliably send messages over many uses of a noisy channel.
For every quantum channel $T$ and every $eps>0$ there exists a threshold $p(epsilon,T)$ for the gate error probability below which rates larger than $C-epsilon$ are fault-tolerantly achievable.
Our results are relevant in communication over large distances, and also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise.
arXiv Detail & Related papers (2020-09-15T15:10:50Z) - Quantum Garbled Circuits [9.937090317971313]
We show how to compute an encoding of a given quantum circuit and quantum input, from which it is possible to derive the output of the computation and nothing else.
Our protocol has the so-called $Sigma$ format with a single-bit challenge, and allows the inputs to be delayed to the last round.
arXiv Detail & Related papers (2020-06-01T17:07:01Z) - 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.