Profile picture
Frédéric Grosshans @fgrosshans
, 28 tweets, 10 min read Read on Twitter
Today’s morning session at the @InHenriPoincare is a tutorial “Verification of Quantum computing” by Elham Kashefi

A recent review: arXiv:1706.06984

Elham Kashefi: Verfication addresses different questions.
1) Test the hardware (tomography like)

2) Test the application: Test is honest behaviour if we use quantum computer for secrecy, test if the answer is correct if we use QC for speed
Elham Kashefi: If a QC solves a classically intractable problem, how can we “verify” the outcome of experiment ?
In complexity ∃MA, Merlin-Arthur: problems who can be verified in BPP when given a proof (aka witness).
But we thing BPQ≠MA.
Even if BQP⊆MA, proof is hard to find
Elham Kashefi: Looking at interacting proofs, IP=QIP: for unlimited prover, a QC doesn’t bring anything to the verifier.
Question: Dose every language ∈BQP admit an IP protocol where the *prover* is restricted to BQP ?

Elham Kashefi: In current verification protocols, either the verifier exchanges qubits with the prover, or the prover has 2 non-communicating but entangled computers
Elham Kashefi:
Open question: ∃? a protocol with single BQP prover interacting classically with a BPP verifier?

Actually, the pb of several non-communicating and non-entangled provers is also open. The previous protocol uses entanglement in the honnest case.
Elham Kashef: All these protocol use the technique of blindness (computing on encrypted data)
cf @jfitzsimons’ arXiv:1611/10107

Idea: delegate computation to remote computer s.t. target comutation is indistinguishable from any other of same length
Elham Kashefi: The client does easy computation (low depth), and the server complex ones.
If the protocol is computationnally secure : (Quantum) Fully Homomorpic Encryption (FHE / QFHE)
If informationally secure: Blindness

Elham Kashefi: For single server verification, several cases:
1) prepare–send client (client : constant size QC)
2) Measuring client
3) Repeated run
Elham Kashefi start to construct a blind protocol using QKD And teleportation. She uses gate teleportation, with a measurement in the XY plane and a random phase θ, compensated in the measurement
Elham Kashefi: schematics of the previous tweet #LTQI
Elham Kashefi then add a random phase rπ (r is 0 or 1) to the measurement and obtains her scheme, with the client preparing the state P(θ)Z^i|+> and making the final bitflip X (taking r into account).
The server does the rest (CZ, measurement)
Elham Kashefi:
rπ prevents a leak from the output.
α defines the computation, but the server only sees δ=α+θ+rπ, which is uniform.
Combining this little gadget with a bunch of control Zs to create a universal graph state allows to make universal blind QC (UBQC)
Elham Kashefi:
For UBQC, Alice should translate the cricuit C into a graph MPQC (G,α). Since the graph could leak some information on the computation, one should use a (potentially wasteful) graph pattern
Elham Kashefi:
The secret is now the set of α .
Alice send the states |+_θ⟩= P(θ)Zⁱ|+⟩ to Bob/Server
Bob creates graph state |G⟩
For each i
Alice sends δ=α+θ+rπ⟩
Bob makes the measurement and obtains b_i and sends it to ALice
Alice computes b⊕r=s, the result

After the coffee break, Elham Kashefi defines ε-verifiability and δ-correctness:
Verification is a protocol where probabilitiy(witness accepted and outcome is bad)≤ε.
Elham Kashefi then formalizes the above definition:
The verifie state is |ψ⟩|flag⟩, where flag∈{acc,rej}. Initally flag=acc
There’s and encoding channel Enc^s depending on verifier channel, depending of private random variable s of verifier
Elham Kashefi:
P_honnest applies a CPTP
ψout^s⟩⟨ψout^s|=Tr_flag( Phonnest(Enc^s|ψ⟩⟨ψ|)⊗|acc⟩⟨acc|))
ε-verifiable⇔ Tr(∑_s p(s) Pincorrect^s P(Enc^s(|ψ⟩⟨ψ|)⊗|acc⟩⟨acc|)))≤ε
Elham Kashefi:
A protocol is δ-correct iff
Tr(∑_s p(s) Pincorrect^s Phonnest(Enc^s(|ψ⟩⟨ψ|)⊗|acc⟩⟨acc|)))≥δ
Elham Kashefi:
The challenge in finding an ε-verifiable verifiable: The P in the middle of the definition is an arbitrary CPTP map, preformed by a dishonnest prover

Elham Kashefi:
A common tool is Clifford Pauli twirling, where C used for encryption/decryption:
∑_C C⁺P₁CρC⁺P₂C =0
with P₁≠P₂ Paulis
sum over either C∈Clifford or C∈Paulis
Elham Kashefi, For any encoding, we have
ℰ(ρ)=∑ Ki ρ Ki⁺ with ∑Ki Ki⁺ =1
Ki = ∑αj Pj
ℰ(ρ)=∑_ijk α_ij α_ik^* Pi ρ Pj⁺
∃ annoying croos terms above: solution=use twirling theorem above
Elham Kashefi:
The encoding Enc introduce a random Clifford/Pauli

ℰ(ρ)=∑a_ij^* Pi ρ Pi

Elham Kashefi:
To make a concrete UBQC protocol, one also need to define a flag:
create a trap, a |+_θ⟩ at random position, surounded with dummy qubits (|0⟩,|1⟩).
The result of the measurement is deterministically r
Elham Kashefi:
The UBQC protocol is then modified into VUBQC.
I. The graph G has to admit T trap-qubits and D dummy-qubits. E.g. consider a cylindrical cluster state, cut by a (random) line of traps into flat cluster states. (∃more efficient graphs)
Elham Kashefi:
Then the qubits are in 3 sets Q (computation) T (trap) D (dummy).
Alice behaves the differently for the different qubits type, as expected.
Then finally, accepts the computation iff the trap qubits gave the expected answer.
Elham Kashefi:
There is a link between ε and he number of traps. Let’s compute ε for one trap. We find 1–1/N, the probability to hit the trap.
With a constant fraction of traps, we have ε=8/9.

For an exponential bound at a linear cost, repeat d times, and ε=(8/9)^d

Elham Kashefi:
This is a universal protocol. If one is only interested to a specific family (IQP, Clean-qubit, etc.) it can be simplified.
It seems to always be possible to adpat this technique, except for CV (no twirling)
Missing some Tweet in this thread?
You can try to force a refresh.

Like this thread? Get email updates or save it to PDF!

Subscribe to Frédéric Grosshans
Profile picture

Get real-time email alerts when new unrolls are available from this author!

This content may be removed anytime!

Twitter may remove this content at anytime, convert it as a PDF, save and print for later use!

Try unrolling a thread yourself!

how to unroll video

1) Follow Thread Reader App on Twitter so you can easily mention us!

2) Go to a Twitter thread (series of Tweets by the same owner) and mention us with a keyword "unroll" @threadreaderapp unroll

You can practice here first or read more on our help page!

Did Thread Reader help you today?

Support us! We are indie developers!

This site is made by just three indie developers on a laptop doing marketing, support and development! Read more about the story.

Become a Premium Member and get exclusive features!

Premium member ($3.00/month or $30.00/year)

Too expensive? Make a small donation by buying us coffee ($5) or help with server cost ($10)

Donate via Paypal Become our Patreon

Thank you for your support!