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?


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.