Abstract

The class quantum Merlin–Arthur (QMA), as the quantum analog of nondeterministic polynomial time, contains the decision problems whose YES instance can be verified efficiently with a quantum computer. The problem of deciding the group non-membership (GNM) of a group element is conjectured to be a member of QMA. Previous works on the verification of GNM, which still lacks experimental demonstration, required a quantum circuit with O(n5) group oracle calls. Here, we provide an efficient way to verify GNM problems, in which each quantum circuit only contains O(1) group of oracle calls, and the number of qubits in each circuit is reduced by half. Based on this protocol, we then experimentally demonstrate the new verification process with a four-element group in an all-optical circuit. The new protocol is validated experimentally by observing a significant completeness-soundness gap between the probabilities of accepting elements in and outside the subgroup. This work efficiently simplifies the verification of GNM and is helpful in constructing more quantum protocols based on the near-term quantum devices.

© 2021 Chinese Laser Press

1. INTRODUCTION

Quantum effect can be used to enhance information processing in many ways. Besides speeding up solving certain problems [13], quantum computers can also be used to construct novel interactive proof systems (IPSs) [46], which leads to fruitful studies in blind quantum computing [79], quantum zero-knowledge proof systems [10,11], and multiprover IPSs [12,13]. An IPS involves a verifier and (potentially multiple) provers, where the verifier aims at solving certain problems by exchanging messages with the provers.

IPSs can be used to classify decision problems, the problems whose answers can only be YES or NO. For example, nondeterministic polynomial time (NP), one of the most important complexity classes, can be described by an IPS, with a classical verifier and a single computationally unbounded prover exchanging one round of classical message [14,15]. Specifically, NP contains decision problems that, for a YES instance, there exists certain proof message, with which the YES instance can be verified in polynomial time by a classical computer. NP can be generalized to the quantum realm naturally and the quantum analog is called quantum Merlin–Arthur (QMA) [15,16]. In QMA, the proof message is replaced by a quantum state, and the verifier can use a quantum computer to process it [17,18].

Since a classical verifier can be simulated by a quantum computer and a classical message can be described by a quantum state, every problem belonging to NP is also in QMA [15,16], i.e., NPQMA. However, it remains an unsolved problem whether QMA is strictly larger than NP, and the group nonmembership (GNM) problem is believed to be a possible candidate that falls in QMA but not in NP [16,1921]. Previous works have shown the potential quantum advantage on verifying YES instances of this problem. It has been proven that the GNM problem is not in NPB [20] for a certain group oracle B. Also, for every B, GNM(B)QMAB has been proven by giving quantum proofs and a verification process that can be efficiently performed by a quantum computer [21]. Furthermore, it is conjectured that certain quantum proofs, which are similar to the one constructed for proving GNM(B)QMAB, can be used in many other decision problems of finite groups, such as the problems of deciding proper subgroups and simple groups [21].

Because of the potential applications of quantum IPS and the growing power of near-term quantum devices [22,23], it has become a meaningful question on how to make quantum IPS more friendly for near-term quantum devices. The verification of GNM is of special importance, as it is closely related to the verification of a wide spectrum of group properties and is expected to present quantum advantage. However, the previous efforts to verify GNM are not favorable for near-term devices, as it requires too deep quantum circuits [21,24], and the related experimental demonstration is absent.

In this work, based on a new protocol, which improves the previous protocol proposed by Watrous [21] and is more friendly to near-term quantum devices, we experimentally show the verification of GNM by an all-optical setup. By sending various photonic quantum proofs to the optical circuits, a significant completeness-soundness gap, which is the difference between the probabilities of accepting elements outside the subgroup and incorrectly accepting elements inside the subgroup, is observed to present the validity of our protocol. For the groups with at most 2n elements, each quantum circuit in the new protocol only requires O(1) group oracle calls, whereas the previous protocol requires O(n5) oracle calls in one circuit. The number of qubits needed is also half-reduced. Our new process makes it easier to use the verification of GNM as a part of near-term quantum applications such as quantum cryptography protocols.

2. THEORETICAL FRAMEWORK

First, we formally revisit the GNM problem here [21]. Let G be a finite group and S=g1,,gk be a subgroup generated by group elements g1,,gkG. Given an element xG, the GNM problem is to decide whether x is outside the subgroup S. If xS, x is a YES instance; otherwise, x is a NO instance. To analyze the problem with minimum assumption on the group, usually the framework of black-box groups [25] is adopted. Following the framework of the quantum group oracle [21], in which the quantum group element labels are a set of mutually orthogonal quantum states, we denote the quantum label corresponding to the group element g by ψg and the space spanned by the quantum labels of elements in G by span{G}:=span{|ψg1ψg2|:g1,g2G}. The quantum group oracle is defined to be able to detect whether a state is in span{G} and carry out right multiplication M(·) as M(g2)|ψg1=|ψg1g2. The quantum proof for the nonmembership can be a uniform superposition of the elements in a co-set αS of the subgroup S for any αG [21], where αS is defined as αS:={αs|sS}. Explicitly, it can be written as

|Qproof=1|S|gαS|ψg,
where |S| is the element number of the subgroup S. This state is invariant under right multiplications of the elements in S because they map the elements in αS bijectively to αS. On the other hand, if xS, the result state is orthogonal to the original one as Qproof|M(x)|Qproof=0, since (αS)x and αS do not share common elements.

Next, we introduce the core quantum circuit, which plays a central role in both the original and new verification process [21]. The core circuit is similar to the swap test circuit and is depicted in Fig. 1. The outcome of the core circuit is defined to be the measurement outcome of the control qubit. We denote by core(x,|Qproof)=s the event of obtaining the measurement outcome s{0,1} in one run of the core circuit with input state |Qproof and group member x. The outcome can show the effect of the multiplication by x on the input state. For core(x,|Qproof), if xS, the outcome can only be 0, as |Qproof is invariant under the multiplication. If xS, the probability of obtaining 1 is 0.5 as the state after multiplication is orthogonal to |Qproof. Therefore, with the proof state, the non-membership of an element can be verified when the outcome 1 is obtained.

 figure: Fig. 1.

Fig. 1. Core circuit. The circuit is similar to the swap test circuit and aims to check whether the input state is invariant under certain group multiplication. With a correct proof state, if xS, the measurement outcome is always 0; if xS, the measurement outcome is 1 with probability 0.5.

Download Full Size | PPT Slide | PDF

However, a malicious prover may send bogus proof states that deviate from Eq. (1) and give incorrect outcomes. Therefore, to ensure the soundness of the verification, the verifier has to do a property check on the received proof state, i.e., check that the state is invariant under the group multiplication M(s) for any sS, so that the elements in S cannot be proven to be outside S. In the original protocol, to verify the proof received is valid, the verifier needs to uniformly sample the subgroup elements in a reversible way and produce a quantum superposition of all the quantum labels,

gSai|g|garbage(g),
where the norm of {ai} should be nearly uniform. The reversible sampling requires O(n5) calls of the group oracle in the quantum circuit [24] and requires the verifier to keep at least two quantum group element labels.

In the new verification process for GNM, we reduce both the circuit depth and qubit number needed by importing the technique we call random state inspection (RSI). In RSI, the prover is required to send m registers that carry copies of a state to the verifier. The verifier randomly selects one register to reserve and applies independent test channels to the other m1 registers to check the property of the states that they carry. If all the m1 registers pass the property checking, the verifier accepts the reserved register for the later verification process. Otherwise, the verifier rejects. We model the test channel as a quantum channel that maps an input register to an output qubit. The verifier measures the output qubit and regards outcome |0 as pass and |1 as fail. One can show that, if all the other registers have passed the test channels, the probability for the reserved register to fail passing the test channel (if tested) can be bounded to 0 at speed O(1/m) even when the m registers are entangled. Denote the density operator of the reserved register and other registers as ρr and ρt, this bound can be written as

Pr(test(ρr)=fail|test(ρt)=pass)<O(1/m).

To show this bound, one just needs to analyze the density matrix of the output state after applying the test channels to all the registers. After testing all the other registers, the verifier can directly apply the later verification process on the reserved register as its property is ensured. By RSI, as the check and use of the proof state can be done in separate circuits, the circuit depth needed in the verification is reduced to that of the property checking or the later verification.

Besides reducing the circuit depth by RSI, we also simplify the property checking process in the original protocol. Rather than using the state in Eq. (2), which needs O(n5) quantum group oracle calls to produce, we propose a simplified new process here. The test channel of the new process starts from sampling an element s of the subgroup S from a nearly uniform distribution with a classical computer by Babai’s algorithm [24]. Here, nearly uniform means the probability for s to be any subgroup elements is in (1/|S|1/22n,1/|S|+1/22n). The second step of the test channel is a core circuit. With the sampled element s, an input state passes the test channel when core(s,ρ)=0. Therefore, in the whole verification process, all the quantum circuits the verifier needs to run are just core circuits with different group elements.

Here, we discuss the completeness and soundness of the new verification protocol. It can be proven that for any element sS and any quantum state ρspan{G}, the probability of incorrectly proving the non-membership of s, i.e., having core(s,ρ)=1, can be bounded as

Pr(core(s,ρ)=1)1Pr(test(ρ)=pass)K(1|S|22n),
where
1K=1cos(|s|22|s|π),
and |s| is the minimal positive number r such that sr equals identity. With this bound, we know that one can bound the error probability Pr(core(s,ρ)=1) to 0 by increasing Pr(test(ρ)=pass), which can be efficiently bounded to 1 with RSI. Therefore, the soundness of the new protocol is ensured. To prove this bound, one just needs to decompose ρ on the basis of quantum labels {|ψg} and study the coefficient of every basis state under the core circuit. The condition of high Pr(test(ρ)=pass) can provide a restriction on the value of Pr(core(s,ρ)=1) and techniques such as the Lagrangian multiplier can be then used to determine its maximal value. To prove the completeness, one just needs to notice that proof states from honest prover can certainly pass the test channels, and the reserved register with the correct state can prove the non-membership, the same as the original protocol. The whole new verification process is listed below.
  • 1. Prover sends m registers with state in Eq. (1) to the verifier, trying to prove gG is not in the subgroup SG. Verifier receives the registers and checks whether their states are in span{G}. If not, reject the proof.
  • 2. Verifier randomly chooses a register to reserve and applies the property checking process to all the other registers as below.
  • 3. Property checking.
    • (a) Verifier samples an element sS with a classical computer by Babai’s algorithm.
    • (b) Verifier applies the core circuit with multiplication by s to the state. Verifier rejects the proof if the outcome is 1.
  • 4. Verifier applies the core circuit with multiplication by g to the reserved register. The GNM of g is verified when the outcome is 1.

To summarize, in our new protocol, we split the property checking of the proof state and the verification after property checking into different circuits by RSI. We also use a new property checking process that requires many fewer quantum resources. As a result, the verifier only needs to run a core circuit, which is shallow, for many times, rather than run a deep circuit with O(n5) group operations. Also, the number of qubits that the verifier needs to keep is halved because the verifier no longer needs to keep a reversibly sampled quantum label.

3. EXPERIMENTAL SETUP AND RESULTS

In this work, an experimental demonstration of our new verification process is carried out. We consider an Abelian group G={A,B|AB=BA,A2=B2=E}. The four elements in G are encoded in the polarization degree of freedom of photons as |ψE=|VH,|ψA=|HV,|ψB=|HH and |ψAB=|VV, in which |H and |V denote the horizontal and vertical polarization of the photons, respectively. They can together span the whole two-qubit Hilbert space. The corresponding multiplication circuits of the four group elements are illustrated in the first line of Fig. 2(a), where the circuit M(g) of each element g satisfies M(g2)|ψg1=|ψg1g2. We then construct the core circuits with these multiplications and map them to the optical interferometer illustrated in Fig. 2(a). For example, the circuit of A transforms |ψE to |ψA, |ψA to |ψE, |ψB to |ψAB, and |ψAB to |ψB. The subgroups we choose are S={E,A} and S={E,AB}. The quantum proof states for S and S used in the experiment are |Qproof=(|ψB+|ψAB)/2=(HH+VV)/2, and |Qproof=(|ψB+|ψA)/2=(HH+HV)/2, respectively.

 figure: Fig. 2.

Fig. 2. Circuit mapping and experimental setup. (a) The circuits for group multiplications in the first line are deduced from the quantum labels for the elements. They are used to construct the core circuits for the verification process in the second line. Optical paths are presented in the third line. Here, two BSs building an MZI are used to play the role of two Hadamard operations on the control qubit, which is realized with the path information. One path is regarded as |0 and the other one is |1. An HWP is placed in |1 path to act as the CNOT gate on the polarization qubit with the optical axis at 45°. (b) Experimental setups. Entangled photon pairs are produced by pumping BBO and using quartz plates (QPs) on the above panel. Two photons are sent to the sides a and b respectively. On each side, an SI, shown on the bottom panel in detail, is constructed to realize the MZI. In an SI, an HWP is placed in |1 path (shown in orange beam and marked as 2) and a phase compensation (PC) crystal is located in |0 (shown in blue beam and marked as 1). A measurement unit (MU) consisting of a QWP, an HWP, a PBS, and a single-photon detector (D) equipped with an interferometer filter (IF) is placed on each output port (marked as 3 and 4) of the SI. Note, in this figure, unitary of multiplying by A is realized. By removing the SI, we can implement different quantum circuits.

Download Full Size | PPT Slide | PDF

In our experiment, |Qproof,|Qproof,|ψA, and |ψB are put into the core circuit with right multiplication by E,A,B, and AB. Our new protocol only requires one core circuit in each quantum circuit. In contrast, if one strictly follows the original protocol, at least five qubits are needed that contain two quantum labels of group elements and one ancillary qubit for reversible group element sampling. One also needs at least three group multiplications in the strict original circuit, whereas the new method only requires one multiplication in each circuit. The full experimental setup of the new protocol is shown in Fig. 2(b). The input states are generated by pumping two identically cut Type I beta-barium-borate (BBO) crystals whose optic axes are aligned in mutually perpendicular planes [26] with an ultraviolet (UV) source. The UV pulses are frequency doubled from a mode-locked Ti:sapphire laser centered at 800 nm with 130 fs pulse width and 76 MHz repetition rate. After compensating the birefringence effect between H and V in BBO crystals with quartz plates (QPs), maximally entangled photon pairs of the forms |Qproof are produced [26]. Furthermore, by adjusting the polarization of pump pulses and downconversion photons, the other states of |ψB=|HH, |ψA=|HV, and |Qproof=(|HH+|HV)/2 are produced. The input photons are then sent to one of the quantum circuits in Fig. 2 to perform the core circuit with different group multiplications.

In our setup, the Mach–Zehnder interferometer (MZI) is realized by a Sagnac interferometer in which the path information of photons is regarded as the control qubit [27]. In a Sagnac interferometer, an optical nonpolarization beam splitter (BS), worked as the Hadamard gates on control qubit, is used to separate the beam into two paths, 1 and 2, which are treated as the control qubit |0 and |1, respectively. Here, the BS is chosen to split 50:50 for 0° angle of incidence, which could decrease the difference of the split ratio of different polarizations. In the path |1, a half-wave plate (HWP) is used to implement CNOT gates set at 45° to reverse the photon polarization. The visibilities of two Sagnac interferometers are 96.7%±0.4% and 95.9%±0.4%, respectively. Note that, for the circuit E with Es multiplication, there is no CNOT gate and the HWP is set at 0°. Beams 1 and 2 combine in the BS and then are separated as beams 3 and 4. The polarization of photons is analyzed on the outputs of beams 3 and 4 by polarization beam splitters (PBSs), HWPs, and quarter-wave plates (QWPs). The photons are detected by single-photon detectors (D) equipped with 3 nm interference filters (IFs).

For the circuit A, which implements the multiplication by A, the probability P0 of detecting |0 equals the sum of the coincidence count (CC) of detectors located at a3 and b3 and the CC of detectors located at a4 and b4, where a3 is the output port 3 of the SI on the side of a, and similarly hereinafter. The probability P1 of detecting |1 equals the sum of the CC of a3 and b4 and the CC of a4 and b3. On the other hand, for the case of circuit B, according to the corresponding mapping relation where the SI is only placed in the a side, the probability of detecting |0 equals the CC of a3 and b, and the probability of |1 equals the CC of a4 and b. Similar methods suit the other circuits AB and E.

Besides the interference visibility introduced above, two SIs are further verified with the input state of (|HH+|VV)/2, which is prepared with a fidelity of 95.9%±1.0%. For the SI appearing in the E circuit, the output state generated from the CC of a3 and b remains the maximally entangled state and is achieved experimentally with a fidelity of 95.3%±1.0%. For the other interferometer that is used in circuit AB, without inserting the CNOT gate, the output state generated from the CC of a and b3 is also the same as the input state and is achieved with a fidelity of 94.2%±1.4%. We further verify other output cases of the interferometers and achieve high fidelities for them. For the input state 12(B+AB)=12(|HH+|VV), we present the detailed experimental real matrix and imaginary matrix of the outputs here, as shown in Figs. 3 and 4.

 figure: Fig. 3.

Fig. 3. Real parts of density matrices of the final output photons for the case with input state of (|HH+|VV)/2. (a)–(c) Cases of initial state, output photons of a3 and b in E-type interferometer, output photons of a and b3 in AB-type interferometer without CNOT gate, respectively; (e)–(g) cases of output photons of a3 and b3 in A-type interferometer (with fidelity 92.6%±2.4%), a3 and b in B-type interferometer (88.9%±0.7%), a and b3 in AB-type interferometer (88.5%±1.2%), respectively; (i)–(k) cases of output photons of a4 and b4 in A-type interferometer (98.0%±0.3%), a4 and b in B-type interferometer (94.4%±0.3%), a and b4 in AB-type interferometer (94.8%±0.9%), respectively; (d), (h), and (l) corresponding theoretical predictions.

Download Full Size | PPT Slide | PDF

 figure: Fig. 4.

Fig. 4. Imaginary parts of density matrices of the final output photons for the case with input state of 12(|HH+|VV). (a)–(c) Cases of initial state, output photons of a3 and b in E-type interferometer, output photons of a and b3 in AB-type interferometer without CNOT gate, respectively; (e)–(g) cases of output photons of a3 and b3 in A-type interferometer, a3 and b in B-type interferometer, a and b3 in AB-type interferometer, respectively; (i)–(k) cases of output photons of a4 and b4 in A-type interferometer, a4 and b in B-type interferometer, a and b4 in AB-type interferometer, respectively; (d), (h), and (l) corresponding theoretical predictions.

Download Full Size | PPT Slide | PDF

Equipped with the experiment setup, we first carried out our new process on the group S. To demonstrate the test channel in our verification process, the correct proof |Qproof as well as the bogus proofs |Qproof,ψA and |ψB is produced and sent to the core circuit with multiplication by A. A state passes the test if the control qubit is detected to be |0. The results are shown in Fig. 5(a). We find that the probabilities for a bogus proof to pass the state test do not exceed 0.518±0.017 and have a significant gap toward the probability 0.955±0.006 for a correct proof state |Qproof to pass. Then we show how the nonmembership of an element g can be verified with the correct proof state |Qproof. The GNM of g is verified when |1 is detected in the core circuit with multiplication by g. The experimental result is shown in Fig. 5(b). We find the probabilities for |Qproof to be accepted are higher than 0.496±0.009 for B,ABS and lower than 0.045±0.006 for E,AS. The above analysis implies that if the prover sends m registers and the verifier chooses m1 registers to test, the probability pc for a group of correct proof state to be accepted is greater than 0.496×(0.955)m1. In contrast, the probability for m bogus state to pass the tests is only (0.518)m1. For a general bogus proof, our theory can show that the probability ps for it to be accepted can be bounded by 167(m1). Therefore, the gap pcps is maximized when m=15 and the maximal value is 0.097.

 figure: Fig. 5.

Fig. 5. Experimental results. (a), (c) Detecting probabilities of |0 with different input proof states for the circuit A and AB, respectively; (b), (d) probability for the proof states |Qproof and |Qproof to prove GNM for every group element (detecting the control qubit in |1). The histograms and black points are theoretical and experimental results, respectively. All error bars are estimated to be standard deviation from the statistical variation of the photon counts, assumed to follow a Poisson distribution.

Download Full Size | PPT Slide | PDF

For the other subgroup S, the result is similar. The bogus proofs become |ψA, |ψB, |Qproof, and the correct proof becomes |Qproof. The probabilities for the bogus proofs to pass the test channel do not exceed 0.503±0.008 and for the correct proof |Qproof, the corresponding probability is 0.980±0.003, as shown in Fig. 5(c). We find that the probability for |Qproof to be accepted when used for verifying GNM is higher than 0.481±0.017 for B,AS and is lower than 0.020±0.003 for E,ABS, as shown in Fig. 5(d). In this case, ps is still bounded by 167(m1) and pc=0.481×(0.980)m1. The gap pcps is maximized when m=19 and the maximal value is 0.207.

These completeness-soundness gaps strongly support the success of verification of GNM in the new protocol. Though the whole proof state contains more qubits, the number of qubits and operations in the circuit that the verifier needs to process at a time, which are more important to near-term devices, are greatly reduced.

4. CONCLUSION

In this work, we experimentally implement a verification process for GNM in an all-optical setup based on an ameliorative protocol in which the required quantum resources are greatly reduced. With multiplication of four group elements implemented by optical circuits, the process is accomplished on two subgroups consisting of two selected elements. As it is very likely that similar verification process of GNM can be used in other problems of finite groups, it will be interesting if this validity were formally proven and experimentally demonstrated. Furthermore, our novel verification process is helpful to construct more quantum protocols, which could be practical for near-term quantum devices.

Funding

National Key Research and Development Program of China (2016YFA0302700, 2017YFA0304100); National Natural Science Foundation of China (11821404, 11774335, 61725504, 61805227, 61975195, U19A2075, 11875160, U1801661); Anhui Initiative in Quantum Information Technologies (AHY060300, AHY020100); Key Research Program of Frontier Science, CAS (QYZDYSSW-SLH003); Science Foundation of the CAS (ZDRW-XH-2019-1); Fundamental Research Funds for the Central Universities (WK2030380017, WK2030380015, WK2470000026); Natural Science Foundation of Guangdong Province (2017B030308003); Key R&D Program of Guangdong Province (2018B030326001); Science, Technology and Innovation Commission of Shenzhen Municipality (JCYJ20170412152620376, JCYJ20170817105046702, KYTDPT20181011104202253); Economy, Trade and Information Commission of Shenzhen Municipality (201901161512); Guangdong Provincial Key Laboratory (2019B121203002).

Disclosures

The authors declare no conflicts of interest.

Data Availability

Data underlying the results presented in this paper are not publicly available at this time but may be obtained from the authors upon reasonable request.

REFERENCES

1. P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in 35th Annual Symposium on Foundations of Computer Science (IEEE, 1994), pp. 124–134.

2. A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, “Exponential algorithmic speedup by a quantum walk,” in 35th Annual ACM Symposium on Theory of Computing (ACM, 2003), pp. 59–68.

3. M. A. Nielsen and I. Chuang, Quantum Computation and Quantum Information (Cambridge University, 2002).

4. S. Goldwasser, S. Micali, and C. Rackoff, “The knowledge complexity of interactive proof systems,” SIAM J. Comput. 18, 186–208 (1989). [CrossRef]  

5. J. Watrous, “PSPACE has constant-round quantum interactive proof systems,” Theor. Comput. Sci. 292, 575–588 (2003). [CrossRef]  

6. F. Centrone, N. Kumar, E. Diamanti, and I. Kerenidis, “Experimental demonstration of quantum advantage for NP verification with limited information,” Nat. Commun. 12, 850 (2021). [CrossRef]  

7. A. Broadbent, J. Fitzsimons, and E. Kashefi, “Universal blind quantum computation,” in 50th Annual IEEE Symposium on Foundations of Computer Science (IEEE, 2009), pp. 517–526.

8. J. F. Fitzsimons and E. Kashefi, “Unconditionally verifiable blind quantum computation,” Phys. Rev. A 96, 012303 (2017). [CrossRef]  

9. S. Barz, J. F. Fitzsimons, E. Kashefi, and P. Walther, “Experimental verification of quantum computation,” Nat. Phys. 9, 727–731 (2013). [CrossRef]  

10. A. Broadbent, Z. Ji, F. Song, and J. Watrous, “Zero-knowledge proof systems for QMA,” in IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2016), pp. 31–40.

11. A. B. Grilo, W. Slofstra, and H. Yuen, “Perfect zero knowledge for quantum multiprover interactive proofs,” in IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2019), pp. 611–635.

12. Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen, “MIP*= RE,” arXiv:2001.04383 (2020).

13. A. Natarajan and J. Wright, “NEEXP is contained in MIP,” in IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2019), pp. 510–518.

14. M. Sipser, “Introduction to the theory of computation,” ACM SIGACT News 27, 27–29 (1996). [CrossRef]  

15. A. Y. Kitaev, A. Shen, and M. N. Vyalyi, Classical and Quantum Computation (American Mathematical Society, 2002).

16. J. Watrous, “Quantum computational complexity,” arXiv:0804.3401 (2008).

17. D. Aharonov and T. Naveh, “Quantum NP - a survey,” arXiv:quant-ph/0210077 (2002).

18. H. Kobayashi, K. Matsumoto, and T. Yamakami, “Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur?” in Algorithms and Computation (Springer, 2003), pp. 189–198.

19. L. Babai, “Trading group theory for randomness,” in 7th Annual ACM Symposium on Theory of Computing (ACM, 1985), pp. 421–429.

20. L. Babai, “Bounded round interactive proofs in finite groups,” SIAM J. Discrete Math. 5, 88–111 (1992). [CrossRef]  

21. J. Watrous, “Succinct quantum proofs for properties of finite groups,” in 41st Annual Symposium on Foundations of Computer Science (IEEE, 2000), pp. 537–546.

22. J. Preskill, “Quantum computing in the NISQ era and beyond,” Quantum 2, 79 (2018). [CrossRef]  

23. F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019). [CrossRef]  

24. L. Babai, “Local expansion of vertex-transitive graphs and random generation in finite groups,” in 23rd Annual ACM Symposium on Theory of Computing (ACM, 1991), pp. 164–174.

25. L. Babai and E. Szemerédi, “On the complexity of matrix group problems I,” in 25th Annual Symposium on Foundations of Computer Science (IEEE, 1984), pp. 229–240.

26. P. G. Kwiat, E. Waks, A. G. White, I. Appelbaum, and P. H. Eberhard, “Ultrabright source of polarization-entangled photons,” Phys. Rev. A 60, R773–R776 (1999). [CrossRef]  

27. K. Sun, X.-J. Ye, Y. Xiao, X.-Y. Xu, Y.-C. Wu, J.-S. Xu, J.-L. Chen, C.-F. Li, and G.-C. Guo, “Demonstration of Einstein-Podolsky-Rosen steering with enhanced subchannel discrimination,” Npj Quantum Inf. 4, 12 (2018). [CrossRef]  

References

  • View by:

  1. P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in 35th Annual Symposium on Foundations of Computer Science (IEEE, 1994), pp. 124–134.
  2. A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, “Exponential algorithmic speedup by a quantum walk,” in 35th Annual ACM Symposium on Theory of Computing (ACM, 2003), pp. 59–68.
  3. M. A. Nielsen and I. Chuang, Quantum Computation and Quantum Information (Cambridge University, 2002).
  4. S. Goldwasser, S. Micali, and C. Rackoff, “The knowledge complexity of interactive proof systems,” SIAM J. Comput. 18, 186–208 (1989).
    [Crossref]
  5. J. Watrous, “PSPACE has constant-round quantum interactive proof systems,” Theor. Comput. Sci. 292, 575–588 (2003).
    [Crossref]
  6. F. Centrone, N. Kumar, E. Diamanti, and I. Kerenidis, “Experimental demonstration of quantum advantage for NP verification with limited information,” Nat. Commun. 12, 850 (2021).
    [Crossref]
  7. A. Broadbent, J. Fitzsimons, and E. Kashefi, “Universal blind quantum computation,” in 50th Annual IEEE Symposium on Foundations of Computer Science (IEEE, 2009), pp. 517–526.
  8. J. F. Fitzsimons and E. Kashefi, “Unconditionally verifiable blind quantum computation,” Phys. Rev. A 96, 012303 (2017).
    [Crossref]
  9. S. Barz, J. F. Fitzsimons, E. Kashefi, and P. Walther, “Experimental verification of quantum computation,” Nat. Phys. 9, 727–731 (2013).
    [Crossref]
  10. A. Broadbent, Z. Ji, F. Song, and J. Watrous, “Zero-knowledge proof systems for QMA,” in IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2016), pp. 31–40.
  11. A. B. Grilo, W. Slofstra, and H. Yuen, “Perfect zero knowledge for quantum multiprover interactive proofs,” in IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2019), pp. 611–635.
  12. Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen, “MIP*= RE,” arXiv:2001.04383 (2020).
  13. A. Natarajan and J. Wright, “NEEXP is contained in MIP,” in IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2019), pp. 510–518.
  14. M. Sipser, “Introduction to the theory of computation,” ACM SIGACT News 27, 27–29 (1996).
    [Crossref]
  15. A. Y. Kitaev, A. Shen, and M. N. Vyalyi, Classical and Quantum Computation (American Mathematical Society, 2002).
  16. J. Watrous, “Quantum computational complexity,” arXiv:0804.3401 (2008).
  17. D. Aharonov and T. Naveh, “Quantum NP - a survey,” arXiv:quant-ph/0210077 (2002).
  18. H. Kobayashi, K. Matsumoto, and T. Yamakami, “Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur?” in Algorithms and Computation (Springer, 2003), pp. 189–198.
  19. L. Babai, “Trading group theory for randomness,” in 7th Annual ACM Symposium on Theory of Computing (ACM, 1985), pp. 421–429.
  20. L. Babai, “Bounded round interactive proofs in finite groups,” SIAM J. Discrete Math. 5, 88–111 (1992).
    [Crossref]
  21. J. Watrous, “Succinct quantum proofs for properties of finite groups,” in 41st Annual Symposium on Foundations of Computer Science (IEEE, 2000), pp. 537–546.
  22. J. Preskill, “Quantum computing in the NISQ era and beyond,” Quantum 2, 79 (2018).
    [Crossref]
  23. F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
    [Crossref]
  24. L. Babai, “Local expansion of vertex-transitive graphs and random generation in finite groups,” in 23rd Annual ACM Symposium on Theory of Computing (ACM, 1991), pp. 164–174.
  25. L. Babai and E. Szemerédi, “On the complexity of matrix group problems I,” in 25th Annual Symposium on Foundations of Computer Science (IEEE, 1984), pp. 229–240.
  26. P. G. Kwiat, E. Waks, A. G. White, I. Appelbaum, and P. H. Eberhard, “Ultrabright source of polarization-entangled photons,” Phys. Rev. A 60, R773–R776 (1999).
    [Crossref]
  27. K. Sun, X.-J. Ye, Y. Xiao, X.-Y. Xu, Y.-C. Wu, J.-S. Xu, J.-L. Chen, C.-F. Li, and G.-C. Guo, “Demonstration of Einstein-Podolsky-Rosen steering with enhanced subchannel discrimination,” Npj Quantum Inf. 4, 12 (2018).
    [Crossref]

2021 (1)

F. Centrone, N. Kumar, E. Diamanti, and I. Kerenidis, “Experimental demonstration of quantum advantage for NP verification with limited information,” Nat. Commun. 12, 850 (2021).
[Crossref]

2019 (1)

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

2018 (2)

J. Preskill, “Quantum computing in the NISQ era and beyond,” Quantum 2, 79 (2018).
[Crossref]

K. Sun, X.-J. Ye, Y. Xiao, X.-Y. Xu, Y.-C. Wu, J.-S. Xu, J.-L. Chen, C.-F. Li, and G.-C. Guo, “Demonstration of Einstein-Podolsky-Rosen steering with enhanced subchannel discrimination,” Npj Quantum Inf. 4, 12 (2018).
[Crossref]

2017 (1)

J. F. Fitzsimons and E. Kashefi, “Unconditionally verifiable blind quantum computation,” Phys. Rev. A 96, 012303 (2017).
[Crossref]

2013 (1)

S. Barz, J. F. Fitzsimons, E. Kashefi, and P. Walther, “Experimental verification of quantum computation,” Nat. Phys. 9, 727–731 (2013).
[Crossref]

2003 (1)

J. Watrous, “PSPACE has constant-round quantum interactive proof systems,” Theor. Comput. Sci. 292, 575–588 (2003).
[Crossref]

1999 (1)

P. G. Kwiat, E. Waks, A. G. White, I. Appelbaum, and P. H. Eberhard, “Ultrabright source of polarization-entangled photons,” Phys. Rev. A 60, R773–R776 (1999).
[Crossref]

1996 (1)

M. Sipser, “Introduction to the theory of computation,” ACM SIGACT News 27, 27–29 (1996).
[Crossref]

1992 (1)

L. Babai, “Bounded round interactive proofs in finite groups,” SIAM J. Discrete Math. 5, 88–111 (1992).
[Crossref]

1989 (1)

S. Goldwasser, S. Micali, and C. Rackoff, “The knowledge complexity of interactive proof systems,” SIAM J. Comput. 18, 186–208 (1989).
[Crossref]

Aharonov, D.

D. Aharonov and T. Naveh, “Quantum NP - a survey,” arXiv:quant-ph/0210077 (2002).

Appelbaum, I.

P. G. Kwiat, E. Waks, A. G. White, I. Appelbaum, and P. H. Eberhard, “Ultrabright source of polarization-entangled photons,” Phys. Rev. A 60, R773–R776 (1999).
[Crossref]

Arute, F.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Arya, K.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Babai, L.

L. Babai, “Bounded round interactive proofs in finite groups,” SIAM J. Discrete Math. 5, 88–111 (1992).
[Crossref]

L. Babai, “Trading group theory for randomness,” in 7th Annual ACM Symposium on Theory of Computing (ACM, 1985), pp. 421–429.

L. Babai, “Local expansion of vertex-transitive graphs and random generation in finite groups,” in 23rd Annual ACM Symposium on Theory of Computing (ACM, 1991), pp. 164–174.

L. Babai and E. Szemerédi, “On the complexity of matrix group problems I,” in 25th Annual Symposium on Foundations of Computer Science (IEEE, 1984), pp. 229–240.

Babbush, R.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Bacon, D.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Bardin, J. C.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Barends, R.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Barz, S.

S. Barz, J. F. Fitzsimons, E. Kashefi, and P. Walther, “Experimental verification of quantum computation,” Nat. Phys. 9, 727–731 (2013).
[Crossref]

Biswas, R.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Boixo, S.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Brandao, F. G. S. L.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Broadbent, A.

A. Broadbent, Z. Ji, F. Song, and J. Watrous, “Zero-knowledge proof systems for QMA,” in IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2016), pp. 31–40.

A. Broadbent, J. Fitzsimons, and E. Kashefi, “Universal blind quantum computation,” in 50th Annual IEEE Symposium on Foundations of Computer Science (IEEE, 2009), pp. 517–526.

Buell, D. A.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Burkett, B.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Centrone, F.

F. Centrone, N. Kumar, E. Diamanti, and I. Kerenidis, “Experimental demonstration of quantum advantage for NP verification with limited information,” Nat. Commun. 12, 850 (2021).
[Crossref]

Chen, J.-L.

K. Sun, X.-J. Ye, Y. Xiao, X.-Y. Xu, Y.-C. Wu, J.-S. Xu, J.-L. Chen, C.-F. Li, and G.-C. Guo, “Demonstration of Einstein-Podolsky-Rosen steering with enhanced subchannel discrimination,” Npj Quantum Inf. 4, 12 (2018).
[Crossref]

Chen, Y.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Chen, Z.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Chiaro, B.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Childs, A. M.

A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, “Exponential algorithmic speedup by a quantum walk,” in 35th Annual ACM Symposium on Theory of Computing (ACM, 2003), pp. 59–68.

Chuang, I.

M. A. Nielsen and I. Chuang, Quantum Computation and Quantum Information (Cambridge University, 2002).

Cleve, R.

A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, “Exponential algorithmic speedup by a quantum walk,” in 35th Annual ACM Symposium on Theory of Computing (ACM, 2003), pp. 59–68.

Collins, R.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Courtney, W.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Deotto, E.

A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, “Exponential algorithmic speedup by a quantum walk,” in 35th Annual ACM Symposium on Theory of Computing (ACM, 2003), pp. 59–68.

Diamanti, E.

F. Centrone, N. Kumar, E. Diamanti, and I. Kerenidis, “Experimental demonstration of quantum advantage for NP verification with limited information,” Nat. Commun. 12, 850 (2021).
[Crossref]

Dunsworth, A.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Eberhard, P. H.

P. G. Kwiat, E. Waks, A. G. White, I. Appelbaum, and P. H. Eberhard, “Ultrabright source of polarization-entangled photons,” Phys. Rev. A 60, R773–R776 (1999).
[Crossref]

Farhi, E.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, “Exponential algorithmic speedup by a quantum walk,” in 35th Annual ACM Symposium on Theory of Computing (ACM, 2003), pp. 59–68.

Fitzsimons, J.

A. Broadbent, J. Fitzsimons, and E. Kashefi, “Universal blind quantum computation,” in 50th Annual IEEE Symposium on Foundations of Computer Science (IEEE, 2009), pp. 517–526.

Fitzsimons, J. F.

J. F. Fitzsimons and E. Kashefi, “Unconditionally verifiable blind quantum computation,” Phys. Rev. A 96, 012303 (2017).
[Crossref]

S. Barz, J. F. Fitzsimons, E. Kashefi, and P. Walther, “Experimental verification of quantum computation,” Nat. Phys. 9, 727–731 (2013).
[Crossref]

Fowler, A.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Foxen, B.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Gidney, C.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Giustina, M.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Goldwasser, S.

S. Goldwasser, S. Micali, and C. Rackoff, “The knowledge complexity of interactive proof systems,” SIAM J. Comput. 18, 186–208 (1989).
[Crossref]

Graff, R.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Grilo, A. B.

A. B. Grilo, W. Slofstra, and H. Yuen, “Perfect zero knowledge for quantum multiprover interactive proofs,” in IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2019), pp. 611–635.

Guerin, K.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Guo, G.-C.

K. Sun, X.-J. Ye, Y. Xiao, X.-Y. Xu, Y.-C. Wu, J.-S. Xu, J.-L. Chen, C.-F. Li, and G.-C. Guo, “Demonstration of Einstein-Podolsky-Rosen steering with enhanced subchannel discrimination,” Npj Quantum Inf. 4, 12 (2018).
[Crossref]

Gutmann, S.

A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, “Exponential algorithmic speedup by a quantum walk,” in 35th Annual ACM Symposium on Theory of Computing (ACM, 2003), pp. 59–68.

Habegger, S.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Harrigan, M. P.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Hartmann, M. J.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Ho, A.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Hoffmann, M.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Huang, T.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Humble, T. S.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Isakov, S. V.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Jeffrey, E.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Ji, Z.

Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen, “MIP*= RE,” arXiv:2001.04383 (2020).

A. Broadbent, Z. Ji, F. Song, and J. Watrous, “Zero-knowledge proof systems for QMA,” in IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2016), pp. 31–40.

Jiang, Z.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Kafri, D.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Kashefi, E.

J. F. Fitzsimons and E. Kashefi, “Unconditionally verifiable blind quantum computation,” Phys. Rev. A 96, 012303 (2017).
[Crossref]

S. Barz, J. F. Fitzsimons, E. Kashefi, and P. Walther, “Experimental verification of quantum computation,” Nat. Phys. 9, 727–731 (2013).
[Crossref]

A. Broadbent, J. Fitzsimons, and E. Kashefi, “Universal blind quantum computation,” in 50th Annual IEEE Symposium on Foundations of Computer Science (IEEE, 2009), pp. 517–526.

Kechedzhi, K.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Kelly, J.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Kerenidis, I.

F. Centrone, N. Kumar, E. Diamanti, and I. Kerenidis, “Experimental demonstration of quantum advantage for NP verification with limited information,” Nat. Commun. 12, 850 (2021).
[Crossref]

Kitaev, A. Y.

A. Y. Kitaev, A. Shen, and M. N. Vyalyi, Classical and Quantum Computation (American Mathematical Society, 2002).

Klimov, P. V.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Knysh, S.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Kobayashi, H.

H. Kobayashi, K. Matsumoto, and T. Yamakami, “Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur?” in Algorithms and Computation (Springer, 2003), pp. 189–198.

Korotkov, A.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Kostritsa, F.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Kumar, N.

F. Centrone, N. Kumar, E. Diamanti, and I. Kerenidis, “Experimental demonstration of quantum advantage for NP verification with limited information,” Nat. Commun. 12, 850 (2021).
[Crossref]

Kwiat, P. G.

P. G. Kwiat, E. Waks, A. G. White, I. Appelbaum, and P. H. Eberhard, “Ultrabright source of polarization-entangled photons,” Phys. Rev. A 60, R773–R776 (1999).
[Crossref]

Landhuis, D.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Li, C.-F.

K. Sun, X.-J. Ye, Y. Xiao, X.-Y. Xu, Y.-C. Wu, J.-S. Xu, J.-L. Chen, C.-F. Li, and G.-C. Guo, “Demonstration of Einstein-Podolsky-Rosen steering with enhanced subchannel discrimination,” Npj Quantum Inf. 4, 12 (2018).
[Crossref]

Lindmark, M.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Lucero, E.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Lyakh, D.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Mandrà, S.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Martinis, J. M.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Matsumoto, K.

H. Kobayashi, K. Matsumoto, and T. Yamakami, “Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur?” in Algorithms and Computation (Springer, 2003), pp. 189–198.

McClean, J. R.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

McEwen, M.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Megrant, A.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Mi, X.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Micali, S.

S. Goldwasser, S. Micali, and C. Rackoff, “The knowledge complexity of interactive proof systems,” SIAM J. Comput. 18, 186–208 (1989).
[Crossref]

Michielsen, K.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Mohseni, M.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Mutus, J.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Naaman, O.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Natarajan, A.

Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen, “MIP*= RE,” arXiv:2001.04383 (2020).

A. Natarajan and J. Wright, “NEEXP is contained in MIP,” in IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2019), pp. 510–518.

Naveh, T.

D. Aharonov and T. Naveh, “Quantum NP - a survey,” arXiv:quant-ph/0210077 (2002).

Neeley, M.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Neill, C.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Neven, H.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Nielsen, M. A.

M. A. Nielsen and I. Chuang, Quantum Computation and Quantum Information (Cambridge University, 2002).

Niu, M. Y.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Ostby, E.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Petukhov, A.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Platt, J. C.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Preskill, J.

J. Preskill, “Quantum computing in the NISQ era and beyond,” Quantum 2, 79 (2018).
[Crossref]

Quintana, C.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Rackoff, C.

S. Goldwasser, S. Micali, and C. Rackoff, “The knowledge complexity of interactive proof systems,” SIAM J. Comput. 18, 186–208 (1989).
[Crossref]

Rieffel, E. G.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Roushan, P.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Rubin, N. C.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Sank, D.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Satzinger, K. J.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Shen, A.

A. Y. Kitaev, A. Shen, and M. N. Vyalyi, Classical and Quantum Computation (American Mathematical Society, 2002).

Shor, P. W.

P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in 35th Annual Symposium on Foundations of Computer Science (IEEE, 1994), pp. 124–134.

Sipser, M.

M. Sipser, “Introduction to the theory of computation,” ACM SIGACT News 27, 27–29 (1996).
[Crossref]

Slofstra, W.

A. B. Grilo, W. Slofstra, and H. Yuen, “Perfect zero knowledge for quantum multiprover interactive proofs,” in IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2019), pp. 611–635.

Smelyanskiy, V.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Song, F.

A. Broadbent, Z. Ji, F. Song, and J. Watrous, “Zero-knowledge proof systems for QMA,” in IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2016), pp. 31–40.

Spielman, D. A.

A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, “Exponential algorithmic speedup by a quantum walk,” in 35th Annual ACM Symposium on Theory of Computing (ACM, 2003), pp. 59–68.

Sun, K.

K. Sun, X.-J. Ye, Y. Xiao, X.-Y. Xu, Y.-C. Wu, J.-S. Xu, J.-L. Chen, C.-F. Li, and G.-C. Guo, “Demonstration of Einstein-Podolsky-Rosen steering with enhanced subchannel discrimination,” Npj Quantum Inf. 4, 12 (2018).
[Crossref]

Sung, K. J.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Szemerédi, E.

L. Babai and E. Szemerédi, “On the complexity of matrix group problems I,” in 25th Annual Symposium on Foundations of Computer Science (IEEE, 1984), pp. 229–240.

Trevithick, M. D.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Vainsencher, A.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Vidick, T.

Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen, “MIP*= RE,” arXiv:2001.04383 (2020).

Villalonga, B.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Vyalyi, M. N.

A. Y. Kitaev, A. Shen, and M. N. Vyalyi, Classical and Quantum Computation (American Mathematical Society, 2002).

Waks, E.

P. G. Kwiat, E. Waks, A. G. White, I. Appelbaum, and P. H. Eberhard, “Ultrabright source of polarization-entangled photons,” Phys. Rev. A 60, R773–R776 (1999).
[Crossref]

Walther, P.

S. Barz, J. F. Fitzsimons, E. Kashefi, and P. Walther, “Experimental verification of quantum computation,” Nat. Phys. 9, 727–731 (2013).
[Crossref]

Watrous, J.

J. Watrous, “PSPACE has constant-round quantum interactive proof systems,” Theor. Comput. Sci. 292, 575–588 (2003).
[Crossref]

A. Broadbent, Z. Ji, F. Song, and J. Watrous, “Zero-knowledge proof systems for QMA,” in IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2016), pp. 31–40.

J. Watrous, “Quantum computational complexity,” arXiv:0804.3401 (2008).

J. Watrous, “Succinct quantum proofs for properties of finite groups,” in 41st Annual Symposium on Foundations of Computer Science (IEEE, 2000), pp. 537–546.

White, A. G.

P. G. Kwiat, E. Waks, A. G. White, I. Appelbaum, and P. H. Eberhard, “Ultrabright source of polarization-entangled photons,” Phys. Rev. A 60, R773–R776 (1999).
[Crossref]

White, T.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Wright, J.

Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen, “MIP*= RE,” arXiv:2001.04383 (2020).

A. Natarajan and J. Wright, “NEEXP is contained in MIP,” in IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2019), pp. 510–518.

Wu, Y.-C.

K. Sun, X.-J. Ye, Y. Xiao, X.-Y. Xu, Y.-C. Wu, J.-S. Xu, J.-L. Chen, C.-F. Li, and G.-C. Guo, “Demonstration of Einstein-Podolsky-Rosen steering with enhanced subchannel discrimination,” Npj Quantum Inf. 4, 12 (2018).
[Crossref]

Xiao, Y.

K. Sun, X.-J. Ye, Y. Xiao, X.-Y. Xu, Y.-C. Wu, J.-S. Xu, J.-L. Chen, C.-F. Li, and G.-C. Guo, “Demonstration of Einstein-Podolsky-Rosen steering with enhanced subchannel discrimination,” Npj Quantum Inf. 4, 12 (2018).
[Crossref]

Xu, J.-S.

K. Sun, X.-J. Ye, Y. Xiao, X.-Y. Xu, Y.-C. Wu, J.-S. Xu, J.-L. Chen, C.-F. Li, and G.-C. Guo, “Demonstration of Einstein-Podolsky-Rosen steering with enhanced subchannel discrimination,” Npj Quantum Inf. 4, 12 (2018).
[Crossref]

Xu, X.-Y.

K. Sun, X.-J. Ye, Y. Xiao, X.-Y. Xu, Y.-C. Wu, J.-S. Xu, J.-L. Chen, C.-F. Li, and G.-C. Guo, “Demonstration of Einstein-Podolsky-Rosen steering with enhanced subchannel discrimination,” Npj Quantum Inf. 4, 12 (2018).
[Crossref]

Yamakami, T.

H. Kobayashi, K. Matsumoto, and T. Yamakami, “Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur?” in Algorithms and Computation (Springer, 2003), pp. 189–198.

Yao, Z. J.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Ye, X.-J.

K. Sun, X.-J. Ye, Y. Xiao, X.-Y. Xu, Y.-C. Wu, J.-S. Xu, J.-L. Chen, C.-F. Li, and G.-C. Guo, “Demonstration of Einstein-Podolsky-Rosen steering with enhanced subchannel discrimination,” Npj Quantum Inf. 4, 12 (2018).
[Crossref]

Yeh, P.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Yuen, H.

Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen, “MIP*= RE,” arXiv:2001.04383 (2020).

A. B. Grilo, W. Slofstra, and H. Yuen, “Perfect zero knowledge for quantum multiprover interactive proofs,” in IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2019), pp. 611–635.

Zalcman, A.

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

ACM SIGACT News (1)

M. Sipser, “Introduction to the theory of computation,” ACM SIGACT News 27, 27–29 (1996).
[Crossref]

Nat. Commun. (1)

F. Centrone, N. Kumar, E. Diamanti, and I. Kerenidis, “Experimental demonstration of quantum advantage for NP verification with limited information,” Nat. Commun. 12, 850 (2021).
[Crossref]

Nat. Phys. (1)

S. Barz, J. F. Fitzsimons, E. Kashefi, and P. Walther, “Experimental verification of quantum computation,” Nat. Phys. 9, 727–731 (2013).
[Crossref]

Nature (1)

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
[Crossref]

Npj Quantum Inf. (1)

K. Sun, X.-J. Ye, Y. Xiao, X.-Y. Xu, Y.-C. Wu, J.-S. Xu, J.-L. Chen, C.-F. Li, and G.-C. Guo, “Demonstration of Einstein-Podolsky-Rosen steering with enhanced subchannel discrimination,” Npj Quantum Inf. 4, 12 (2018).
[Crossref]

Phys. Rev. A (2)

P. G. Kwiat, E. Waks, A. G. White, I. Appelbaum, and P. H. Eberhard, “Ultrabright source of polarization-entangled photons,” Phys. Rev. A 60, R773–R776 (1999).
[Crossref]

J. F. Fitzsimons and E. Kashefi, “Unconditionally verifiable blind quantum computation,” Phys. Rev. A 96, 012303 (2017).
[Crossref]

Quantum (1)

J. Preskill, “Quantum computing in the NISQ era and beyond,” Quantum 2, 79 (2018).
[Crossref]

SIAM J. Comput. (1)

S. Goldwasser, S. Micali, and C. Rackoff, “The knowledge complexity of interactive proof systems,” SIAM J. Comput. 18, 186–208 (1989).
[Crossref]

SIAM J. Discrete Math. (1)

L. Babai, “Bounded round interactive proofs in finite groups,” SIAM J. Discrete Math. 5, 88–111 (1992).
[Crossref]

Theor. Comput. Sci. (1)

J. Watrous, “PSPACE has constant-round quantum interactive proof systems,” Theor. Comput. Sci. 292, 575–588 (2003).
[Crossref]

Other (16)

P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in 35th Annual Symposium on Foundations of Computer Science (IEEE, 1994), pp. 124–134.

A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, “Exponential algorithmic speedup by a quantum walk,” in 35th Annual ACM Symposium on Theory of Computing (ACM, 2003), pp. 59–68.

M. A. Nielsen and I. Chuang, Quantum Computation and Quantum Information (Cambridge University, 2002).

A. Broadbent, Z. Ji, F. Song, and J. Watrous, “Zero-knowledge proof systems for QMA,” in IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2016), pp. 31–40.

A. B. Grilo, W. Slofstra, and H. Yuen, “Perfect zero knowledge for quantum multiprover interactive proofs,” in IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2019), pp. 611–635.

Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen, “MIP*= RE,” arXiv:2001.04383 (2020).

A. Natarajan and J. Wright, “NEEXP is contained in MIP,” in IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2019), pp. 510–518.

J. Watrous, “Succinct quantum proofs for properties of finite groups,” in 41st Annual Symposium on Foundations of Computer Science (IEEE, 2000), pp. 537–546.

A. Broadbent, J. Fitzsimons, and E. Kashefi, “Universal blind quantum computation,” in 50th Annual IEEE Symposium on Foundations of Computer Science (IEEE, 2009), pp. 517–526.

A. Y. Kitaev, A. Shen, and M. N. Vyalyi, Classical and Quantum Computation (American Mathematical Society, 2002).

J. Watrous, “Quantum computational complexity,” arXiv:0804.3401 (2008).

D. Aharonov and T. Naveh, “Quantum NP - a survey,” arXiv:quant-ph/0210077 (2002).

H. Kobayashi, K. Matsumoto, and T. Yamakami, “Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur?” in Algorithms and Computation (Springer, 2003), pp. 189–198.

L. Babai, “Trading group theory for randomness,” in 7th Annual ACM Symposium on Theory of Computing (ACM, 1985), pp. 421–429.

L. Babai, “Local expansion of vertex-transitive graphs and random generation in finite groups,” in 23rd Annual ACM Symposium on Theory of Computing (ACM, 1991), pp. 164–174.

L. Babai and E. Szemerédi, “On the complexity of matrix group problems I,” in 25th Annual Symposium on Foundations of Computer Science (IEEE, 1984), pp. 229–240.

Data Availability

Data underlying the results presented in this paper are not publicly available at this time but may be obtained from the authors upon reasonable request.

Cited By

Optica participates in Crossref's Cited-By Linking service. Citing articles from Optica Publishing Group journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (5)

Fig. 1.
Fig. 1. Core circuit. The circuit is similar to the swap test circuit and aims to check whether the input state is invariant under certain group multiplication. With a correct proof state, if xS, the measurement outcome is always 0; if xS, the measurement outcome is 1 with probability 0.5.
Fig. 2.
Fig. 2. Circuit mapping and experimental setup. (a) The circuits for group multiplications in the first line are deduced from the quantum labels for the elements. They are used to construct the core circuits for the verification process in the second line. Optical paths are presented in the third line. Here, two BSs building an MZI are used to play the role of two Hadamard operations on the control qubit, which is realized with the path information. One path is regarded as |0 and the other one is |1. An HWP is placed in |1 path to act as the CNOT gate on the polarization qubit with the optical axis at 45°. (b) Experimental setups. Entangled photon pairs are produced by pumping BBO and using quartz plates (QPs) on the above panel. Two photons are sent to the sides a and b respectively. On each side, an SI, shown on the bottom panel in detail, is constructed to realize the MZI. In an SI, an HWP is placed in |1 path (shown in orange beam and marked as 2) and a phase compensation (PC) crystal is located in |0 (shown in blue beam and marked as 1). A measurement unit (MU) consisting of a QWP, an HWP, a PBS, and a single-photon detector (D) equipped with an interferometer filter (IF) is placed on each output port (marked as 3 and 4) of the SI. Note, in this figure, unitary of multiplying by A is realized. By removing the SI, we can implement different quantum circuits.
Fig. 3.
Fig. 3. Real parts of density matrices of the final output photons for the case with input state of (|HH+|VV)/2. (a)–(c) Cases of initial state, output photons of a3 and b in E-type interferometer, output photons of a and b3 in AB-type interferometer without CNOT gate, respectively; (e)–(g) cases of output photons of a3 and b3 in A-type interferometer (with fidelity 92.6%±2.4%), a3 and b in B-type interferometer (88.9%±0.7%), a and b3 in AB-type interferometer (88.5%±1.2%), respectively; (i)–(k) cases of output photons of a4 and b4 in A-type interferometer (98.0%±0.3%), a4 and b in B-type interferometer (94.4%±0.3%), a and b4 in AB-type interferometer (94.8%±0.9%), respectively; (d), (h), and (l) corresponding theoretical predictions.
Fig. 4.
Fig. 4. Imaginary parts of density matrices of the final output photons for the case with input state of 12(|HH+|VV). (a)–(c) Cases of initial state, output photons of a3 and b in E-type interferometer, output photons of a and b3 in AB-type interferometer without CNOT gate, respectively; (e)–(g) cases of output photons of a3 and b3 in A-type interferometer, a3 and b in B-type interferometer, a and b3 in AB-type interferometer, respectively; (i)–(k) cases of output photons of a4 and b4 in A-type interferometer, a4 and b in B-type interferometer, a and b4 in AB-type interferometer, respectively; (d), (h), and (l) corresponding theoretical predictions.
Fig. 5.
Fig. 5. Experimental results. (a), (c) Detecting probabilities of |0 with different input proof states for the circuit A and AB, respectively; (b), (d) probability for the proof states |Qproof and |Qproof to prove GNM for every group element (detecting the control qubit in |1). The histograms and black points are theoretical and experimental results, respectively. All error bars are estimated to be standard deviation from the statistical variation of the photon counts, assumed to follow a Poisson distribution.

Equations (5)

Equations on this page are rendered with MathJax. Learn more.

|Qproof=1|S|gαS|ψg,
gSai|g|garbage(g),
Pr(test(ρr)=fail|test(ρt)=pass)<O(1/m).
Pr(core(s,ρ)=1)1Pr(test(ρ)=pass)K(1|S|22n),
1K=1cos(|s|22|s|π),

Metrics