Thread by @fgrosshans

Seated for Elham Kashefi’s HAbilitation à Diriger des Recherches on “Verification of Quantum Computing”

Elham Kashefi is interested in the verification of problems in BQP, but out of NP: Quantum simulation, Jones polynomial, Boson sampling, etc. By definition, problems in NP are verifiable

#LTQI

Elham Kashefi’s method is based on measurement based quantum computing (MBQC), were an entangled resource state is measured adaptively under control of a classical computer.
It reduces the quantum computation to a “quantum Pacman” [sic] eating the qubits one by one #LTQI

Elham Kashefi: “the angle of the mouth of Pacman depends on the result of the previous measurement” #LTQI

Elham Kashefi: In this model, hiding requirement are minimal : single encrypted qubits + classical bits leads to blind computing with unconditional perfect privacy. #LTQI

Elham Kashefi: θ is a random multiple of π/4, the qubit is send as |0⟩+ e^iθ|1⟩, and the measurement angle m is one time padded and performed by the server through gate teleportation
#LTQI

Elham Kashefi: this encryption reduces verification to error detection.
Formally, she wants a mechanisme bounding the probability to accept the result while it is bad, for na arbitrary CPTP map Ω.
The cryptographic toolkit allows to reduce any Ω to a small test subspace #LTQI

Elham Kashefi’s technique is based on embedding “trap qubits” in the computation.
The verification cost is an overhead linear in the size of computation, provided on has perfect randomness and qubit preparation #LTQI

Elham Kashefi: the need for perfect randomness can lifted by playing with several servers, with various (usually high) complexity costs und different assumptions. #LTQI

Elham KAshefi: Verifiable Universal Blind QC can reduce the assumptions needed for secure multiparty QC.
It can be used to adapt Yao garbled circuits for secure 2-party computation to QC. It has uncoditional security wothout need of OT agains honnest but curious adcersary #LTQI

Elham Kashefi ahse worked recently on efficient (low communication) classical SMPC using quantum tools #LTQI

Following question from the jury, Elham Kashefi comes back to the slides on verification with different servers. I can quantify more what is meant by high complexity : O(N⁸⁹¹²) [sic] in some cases, improved in some conditions to O(N²²) and O(N¹³) #LTQI

Elham Kashefi cleverly scheduled her Habilitation one of the very few days we have enough snow in Paris to keep the champagne cold!