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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/139268 |
| _version_ | 1811082016453558272 |
|---|---|
| author | Joshi, Malvika |
| author2 | Harrow, Aram |
| author_facet | Harrow, Aram Joshi, Malvika |
| author_sort | Joshi, Malvika |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T11:56:03Z |
| format | Thesis |
| id | mit-1721.1/139268 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:56:03Z |
| publishDate | 2022 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1392682022-01-15T03:37:29Z Pretending to be Quantum: A study of IQP-based tests of quantumness Joshi, Malvika Harrow, Aram Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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. M.Eng. 2022-01-14T15:00:31Z 2022-01-14T15:00:31Z 2021-06 2021-06-17T20:13:25.553Z Thesis https://hdl.handle.net/1721.1/139268 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Joshi, Malvika Pretending to be Quantum: A study of IQP-based tests of quantumness |
| title | Pretending to be Quantum: A study of IQP-based tests of quantumness |
| title_full | Pretending to be Quantum: A study of IQP-based tests of quantumness |
| title_fullStr | Pretending to be Quantum: A study of IQP-based tests of quantumness |
| title_full_unstemmed | Pretending to be Quantum: A study of IQP-based tests of quantumness |
| title_short | Pretending to be Quantum: A study of IQP-based tests of quantumness |
| title_sort | pretending to be quantum a study of iqp based tests of quantumness |
| url | https://hdl.handle.net/1721.1/139268 |
| work_keys_str_mv | AT joshimalvika pretendingtobequantumastudyofiqpbasedtestsofquantumness |