On the complexity and verification of quantum random circuit sampling

Adam Bouland; Bill Fefferman; Chinmay Nirkhe; Umesh Vazirani

doi:10.1038/s41567-018-0318-2

Keywords

QuantumVerifiable secret sharingComputational complexity theoryQuantum complexity theoryMeasure (data warehouse)Sampling (signal processing)Computer scienceQuantum computerMathematicsStatistical physicsAlgorithmQuantum mechanicsPhysicsTelecommunications

Affiliated Institutions

University of California, Berkeley US

Related Publications

Complexity-Theoretic Foundations of Quantum Supremacy Experiments

Scott Aaronson , Lijie Chen

In the near future, there will likely be special-purpose quantum computers with 40-50 high-quality qubits. This paper lays general theoretical foundations for how to use such de...

2017 Leibniz-Zentrum für Informatik (Schlo... 53 citations

Theoretical Limitations on the Rate of Transmission of Information

W. G. Tuller

A review of early work on the theory of the transmission of information is followed by a critical survey of this work and a refutation of the point that, in the absence of noise...

1949 Proceedings of the IRE 52 citations

Quantum circuit complexity

Andrew Chi-Chih Yao

We propose a complexity model of quantum circuits analogous to the standard (acyclic) Boolean circuit model. It is shown that any function computable in polynomial time by a qua...

2002 Proceedings of 1993 IEEE 34th Annual ... 633 citations

On the Power of Quantum Computation

Daniel Simón

The quantum model of computation is a model, analogous to the probabilistic Turing machine (PTM), in which the normal laws of chance are replaced by those obeyed by particles on...

1997 SIAM Journal on Computing 1261 citations

Complexity, Entropy And The Physics Of Information

W. H. Zurek

This book has emerged from a meeting held during the week of May 29 to June 2, 1989, at St. John’s College in Santa Fe under the auspices of the Santa Fe Institute. The (approxi...

2018 1352 citations

Publication Info

Year: 2018
Type: article
Volume: 15
Issue: 2
Pages: 159-163
Citations: 272
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

On the complexity and verification of quantum random circuit sampling

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

272

OpenAlex

Cite This

APA Style

                            
                                
                                    Adam Bouland, 
                                
                                    Bill Fefferman, 
                                
                                    Chinmay Nirkhe
                                
                                et al.
                            
                            (2018). 
                            On the complexity and verification of quantum random circuit sampling. 
                            Nature Physics
                            , 15
                            (2)
                            , 159-163.
                            https://doi.org/10.1038/s41567-018-0318-2
                        

Identifiers

DOI: 10.1038/s41567-018-0318-2