CASC2017

   

   
    Invited Talks

 

Maurice R. Kibler (Lyon)

Institut de Physique Nucléaire de Lyon, France

 

On the use of Galois fields and Galois rings in quantum information:

 

The notion of mutually unbiased bases (MUBs), which generalize the eigen-bases of the three Pauli matrices in quantum mechanics, plays an important role in the theory of quantum information. Two different bases of a d-dimensional Hilbert space are said to be unbiased if the inner product of any vector of one basis with any vector of the other is equal to 1/√d. From the point of view of quantum mechanics, MUBs are connected to the Heisenberg uncertainty principle. It is known that the maximum number N(d) of MUBs in dimension d is such that N(d)≤d+1 Furthermore, N(d)=d+1 if d is the power of an integer. (As an open problem, it is not known if N(d)=d+1 can be reached when d is a composite number different from the power of a prime.)

The aim of this talk is to show the interest of MUBs in quantum information and to review different methods of constructing MUBs with a special emphasis on the use of Galois fields (for d power of an odd integer) and Galois rings (for d power of an even integer).


 

Jean-Guillaume Dumas (Grenoble)

Laboratoire Jean Kuntzmann, Grenoble, France

 

Prover efficient verifiable computing:

 

In an emerging computing paradigm, computational capabilities, from processing power to storage capacities, are offered to users over communication networks as a service. Amazon Web services (through the Elastic Compute Cloud), Google Compute Engine, or IBM Platform Computing for instance, provide decentralized high-performance computing solutions. The idea is to outsource demanding computations in order to limit infrastructure costs. None of these platforms, however, offer any guarantee whatsoever on the calculation: no guarantee that the result is correct, nor even that the computation has even effectively been done.

The idea of verifiable computing is to associate a data structure to the result that allows a verification algorithm to prove the validity of a result, faster than by recomputing it. It is thus possible to outsource the computations to any "cloud" and to verify afterwards that the computations have been correctly made. We thus talk about a Prover (the server performing the computations) and a Verifier. Goldwasser, Kalai and Rothblum gave in 2008 a generic method to verify any parallelizable computation, in almost linear time in the size of the inputs and the result. However the extra cost of the computations for the Prover (and therefore the extra cost to the customer), although only almost a constant factor of the overall work, is nonetheless prohibitive in practice.

Differently, we will present ad-hoc procedures, e.g. for exact linear algebra computations, that are Prover-efficient, that is that have much less financial overhead.