I'm currently reading Mahadev's paper Classical Homomorphic Encryption for Quantum Circuits: https://arxiv.org/abs/1708.02130
I was told that Mahadev's scheme is not something that can be implemented in the NISQ era, but I couldn't find anything in her paper specifying why this is the case.
My question: can anyone point at some specific ingredients in Mahadev's construction that are problematic for NISQ era computing?
There are two arguments for why it is not possible to use NISQ to implement Mahadev's scheme.
The first one is that it is not intrinsically tolerant to errors. Meaning that very quickly on a NISQ computer the computation will accumulate errors and give noisy outputs.
The second is that to ensure security of the scheme, it must be intractable for the server to solve the computational problem it is based on. This imposes a lower bound on the number of quantum systems used in the scheme because if the full quantum evolution could be classically simulated then there would not be security. Currently NISQ devices are at the simulation-limit. This means that to encode a single qubit you would need to use up all the noisy qubits your Q. computer has. Then you'd be left with nothing to perform an interesting computation.
