Pretending to be Quantum: A study of IQP-based tests of quantumness

We examine the IQP protocol for verifying quantumness presented by Shepherd and Bremner in 2009 [SB09]. In this protocol, the classical verifier sends a prover an IQP circuit and expects back samples from its output distribution as evidence that the prover has quantum capabilities. To test that the samples indeed came from the circuit, the verifier checks that they are consistent with the bias of the output distribution of the circuit in the direction of a secret string s. This bias is given by (1 + 2−𝑔/2 )/2 where 𝑔 is a parameter associated with the Hamiltonian 𝐻 and s [YC20]. We study this parameter and give a strategy for forging samples to fool the verifier into believing that a classical prover is quantum, with a constant probability dependent on 𝑔. We also give a natural method for constructing random circuits with a particular value of 𝑔, either 𝑔 = 0 or 𝑔 = 1. We use the classical forging strategy, along with the construction methods to show that when 𝑔 is small, an adversary can extract s from just 𝐻 and forge samples to fool the verifier with high probability. We give heuristic arguments for the validity of these attacks and demonstrate their success numerically.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2021

Author dc:creator

• Joshi, Malvika

Advisor dc:contributor.advisor

• Harrow, Aram

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/139268

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/139268