827 lines
33 KiB
BibTeX
827 lines
33 KiB
BibTeX
@book{Homer2001,
|
|
doi = {10.1007/978-1-4757-3544-4},
|
|
url = {https://doi.org/10.1007/978-1-4757-3544-4},
|
|
year = {2001},
|
|
publisher = {Springer New York},
|
|
author = {Steven Homer and Alan L. Selman},
|
|
title = {Computability and Complexity Theory}
|
|
}
|
|
|
|
@book{Nielsen2012,
|
|
doi = {10.1017/cbo9780511976667},
|
|
url = {https://doi.org/10.1017/cbo9780511976667},
|
|
year = {2012},
|
|
month = jun,
|
|
publisher = {Cambridge University Press},
|
|
author = {Michael A. Nielsen and Isaac L. Chuang},
|
|
title = {Quantum Computation and Quantum Information}
|
|
}
|
|
|
|
@book{arora2009computational,
|
|
title = {Computational Complexity: A Modern Approach},
|
|
author = {Arora, S. and Barak, B.},
|
|
isbn = {9780521424264},
|
|
lccn = {2009002789},
|
|
url = {https://books.google.pt/books?id=8Wjqvsoo48MC},
|
|
year = {2009},
|
|
publisher = {Cambridge University Press}
|
|
}
|
|
|
|
@inproceedings{Bernstein1993,
|
|
doi = {10.1145/167088.167097},
|
|
url = {https://doi.org/10.1145/167088.167097},
|
|
year = {1993},
|
|
publisher = {{ACM} Press},
|
|
author = {Ethan Bernstein and Umesh Vazirani},
|
|
title = {Quantum complexity theory},
|
|
booktitle = {Proceedings of the twenty-fifth annual {ACM} symposium on Theory of computing - {STOC} {\textquotesingle}93}
|
|
}
|
|
|
|
@inproceedings{Chen2017,
|
|
author = {Aaronson, Scott and Chen, Lijie},
|
|
title = {Complexity-Theoretic Foundations of Quantum Supremacy Experiments},
|
|
year = {2017},
|
|
isbn = {9783959770408},
|
|
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
|
|
address = {Dagstuhl, DEU},
|
|
abstract = {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 devices to demonstrate "quantum supremacy": that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended Church-Turing Thesis as confidently as possible.First, we study the hardness of sampling the output distribution of a random quantum circuit, along the lines of a recent proposal by the Quantum AI group at Google. We show that there's a natural average-case hardness assumption, which has nothing to do with sampling, yet implies that no polynomial-time classical algorithm can pass a statistical test that the quantum sampling procedure's outputs do pass. Compared to previous work -- for example, on BosonSampling and IQP -- the central advantage is that we can now talk directly about the observed outputs, rather than about the distribution being sampled.Second, in an attempt to refute our hardness assumption, we give a new algorithm, inspired by Savitch's Theorem, for simulating a general quantum circuit with n qubits and depth d in polynomial space and dO(n) time. We then discuss why this and other known algorithms fail to refute our assumption.Third, resolving an open problem of Aaronson and Arkhipov, we show that any strong quantum supremacy theorem -- of the form "if approximate quantum sampling is classically easy, then the polynomial hierarchy collapses"-- must be non-relativizing. This sharply contrasts with the situation for exact sampling.Fourth, refuting a conjecture by Aaronson and Ambainis, we show that there is a sampling task, namely Fourier Sampling, with a 1 versus linear separation between its quantum and classical query complexities.Fifth, in search of a "happy medium" between black-box and non-black-box arguments, we study quantum supremacy relative to oracles in P/poly. Previous work implies that, if one-way functions exist, then quantum supremacy is possible relative to such oracles. We show, conversely, that some computational assumption is needed: if SampBPP = SampBQP and NP ⊆ BPP, then quantum supremacy is impossible relative to oracles with small circuits.},
|
|
booktitle = {Proceedings of the 32nd Computational Complexity Conference},
|
|
articleno = {22},
|
|
numpages = {67},
|
|
keywords = {computational complexity, quantum supremacy, quantum computing},
|
|
location = {Riga, Latvia},
|
|
series = {CCC '17}
|
|
}
|
|
|
|
@inproceedings{Shor1994,
|
|
doi = {10.1109/sfcs.1994.365700},
|
|
url = {https://doi.org/10.1109/sfcs.1994.365700},
|
|
publisher = {{IEEE} Comput. Soc. Press},
|
|
author = {P.W. Shor},
|
|
title = {Algorithms for quantum computation: discrete logarithms and factoring},
|
|
booktitle = {Proceedings 35th Annual Symposium on Foundations of Computer Science},
|
|
year = {1994}
|
|
}
|
|
|
|
@unpublished{Kitaev1995,
|
|
title = {Quantum measurements and the Abelian Stabilizer Problem},
|
|
author = {Kitaev, A. Yu.},
|
|
year = {1995},
|
|
eprint = {9511026},
|
|
doi = {10.48550/ARXIV.QUANT-PH/9511026},
|
|
archiveprefix = {arXiv},
|
|
primaryclass = {quant-ph},
|
|
note = {Unpublished},
|
|
keywords = {Quantum Physics (quant-ph), FOS: Physical sciences, FOS: Physical sciences},
|
|
copyright = {Assumed arXiv.org perpetual, non-exclusive license to distribute this article for submissions made before January 2004}
|
|
}
|
|
|
|
@article{Arute2019,
|
|
doi = {10.1038/s41586-019-1666-5},
|
|
url = {https://doi.org/10.1038/s41586-019-1666-5},
|
|
year = {2019},
|
|
month = oct,
|
|
publisher = {Springer Science and Business Media {LLC}},
|
|
volume = {574},
|
|
number = {7779},
|
|
pages = {505--510},
|
|
author = {Frank Arute and Kunal Arya and Ryan Babbush and Dave Bacon and Joseph C. Bardin and Rami Barends and Rupak Biswas and Sergio Boixo and Fernando G. S. L. Brandao and David A. Buell and Brian Burkett and Yu Chen and Zijun Chen and Ben Chiaro and Roberto Collins and William Courtney and Andrew Dunsworth and Edward Farhi and Brooks Foxen and Austin Fowler and Craig Gidney and Marissa Giustina and Rob Graff and Keith Guerin and Steve Habegger and Matthew P. Harrigan and Michael J. Hartmann and Alan Ho and Markus Hoffmann and Trent Huang and Travis S. Humble and Sergei V. Isakov and Evan Jeffrey and Zhang Jiang and Dvir Kafri and Kostyantyn Kechedzhi and Julian Kelly and Paul V. Klimov and Sergey Knysh and Alexander Korotkov and Fedor Kostritsa and David Landhuis and Mike Lindmark and Erik Lucero and Dmitry Lyakh and Salvatore Mandr{\`{a}} and Jarrod R. McClean and Matthew McEwen and Anthony Megrant and Xiao Mi and Kristel Michielsen and Masoud Mohseni and Josh Mutus and Ofer Naaman and Matthew Neeley and Charles Neill and Murphy Yuezhen Niu and Eric Ostby and Andre Petukhov and John C. Platt and Chris Quintana and Eleanor G. Rieffel and Pedram Roushan and Nicholas C. Rubin and Daniel Sank and Kevin J. Satzinger and Vadim Smelyanskiy and Kevin J. Sung and Matthew D. Trevithick and Amit Vainsencher and Benjamin Villalonga and Theodore White and Z. Jamie Yao and Ping Yeh and Adam Zalcman and Hartmut Neven and John M. Martinis},
|
|
title = {Quantum supremacy using a programmable superconducting processor},
|
|
journal = {Nature}
|
|
}
|
|
|
|
@article{Terhal2018,
|
|
doi = {10.1038/s41567-018-0131-y},
|
|
url = {https://doi.org/10.1038/s41567-018-0131-y},
|
|
year = {2018},
|
|
month = apr,
|
|
publisher = {Springer Science and Business Media {LLC}},
|
|
volume = {14},
|
|
number = {6},
|
|
pages = {530--531},
|
|
author = {Barbara M. Terhal},
|
|
title = {Quantum supremacy, here we come},
|
|
journal = {Nature Physics}
|
|
}
|
|
|
|
@inproceedings{Haner2017,
|
|
doi = {10.1145/3126908.3126947},
|
|
url = {https://doi.org/10.1145/3126908.3126947},
|
|
year = {2017},
|
|
month = nov,
|
|
publisher = {{ACM}},
|
|
author = {Thomas H\"{a}ner and Damian S. Steiger},
|
|
title = {0.5 petabyte simulation of a 45-qubit quantum circuit},
|
|
booktitle = {Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis}
|
|
}
|
|
|
|
@unpublished{Markov2018,
|
|
title = {Quantum Supremacy Is Both Closer and Farther than It Appears},
|
|
author = {Igor Markov and Aneeqa Fatima and Sergei Isakov and Sergio Boixo},
|
|
year = {2018},
|
|
eprint = {1807.10749},
|
|
archiveprefix = {arXiv},
|
|
primaryclass = {quant-ph},
|
|
note = {Unpublished}
|
|
}
|
|
|
|
@article{Bravyi2016,
|
|
doi = {10.1103/physrevlett.116.250501},
|
|
url = {https://doi.org/10.1103/physrevlett.116.250501},
|
|
year = {2016},
|
|
month = jun,
|
|
publisher = {American Physical Society ({APS})},
|
|
volume = {116},
|
|
number = {25},
|
|
author = {Sergey Bravyi and David Gosset},
|
|
title = {Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates},
|
|
journal = {Physical Review Letters}
|
|
}
|
|
|
|
@article{VandenNest2010,
|
|
doi = {10.26421/qic10.3-4-6},
|
|
url = {https://doi.org/10.26421/qic10.3-4-6},
|
|
year = {2010},
|
|
month = mar,
|
|
publisher = {Rinton Press},
|
|
volume = {10},
|
|
number = {3{\&}4},
|
|
pages = {258--271},
|
|
author = {M. Van den Nest},
|
|
title = {Classical simulation of quantum computation, the gottesman-Knill theorem, and slightly beyond},
|
|
journal = {Quantum Information and Computation}
|
|
}
|
|
|
|
@book{Gottesman1999,
|
|
title = {Group22: Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics, Hobart, July 13-17, 1998},
|
|
author = {Corney, S.P. and Delbourgo, R. and Jarvis, P.D.},
|
|
pages = {{32}--{43}},
|
|
isbn = {9781571460547},
|
|
series = {International Press lectures and conference proceedings in physics},
|
|
url = {https://books.google.pt/books?id=YPH4PgAACAAJ},
|
|
year = {1999},
|
|
publisher = {International Press}
|
|
}
|
|
|
|
@article{Gottesman2004,
|
|
title = {Improved simulation of stabilizer circuits},
|
|
author = {Aaronson, Scott and Gottesman, Daniel},
|
|
journal = {Phys. Rev. A},
|
|
volume = {70},
|
|
issue = {5},
|
|
pages = {052328},
|
|
numpages = {14},
|
|
year = {2004},
|
|
month = {Nov},
|
|
publisher = {American Physical Society},
|
|
doi = {10.1103/PhysRevA.70.052328},
|
|
url = {https://link.aps.org/doi/10.1103/PhysRevA.70.052328}
|
|
}
|
|
|
|
@article{Bravyi2005,
|
|
doi = {10.1103/physreva.71.022316},
|
|
url = {https://doi.org/10.1103/physreva.71.022316},
|
|
year = {2005},
|
|
month = feb,
|
|
publisher = {American Physical Society ({APS})},
|
|
volume = {71},
|
|
number = {2},
|
|
author = {Sergey Bravyi and Alexei Kitaev},
|
|
title = {Universal quantum computation with ideal Clifford gates and noisy ancillas},
|
|
journal = {Physical Review A}
|
|
}
|
|
|
|
@article{DeRaedt2019,
|
|
doi = {10.1016/j.cpc.2018.11.005},
|
|
url = {https://doi.org/10.1016/j.cpc.2018.11.005},
|
|
year = {2019},
|
|
month = apr,
|
|
publisher = {Elsevier {BV}},
|
|
volume = {237},
|
|
pages = {47--61},
|
|
author = {Hans De Raedt and Fengping Jin and Dennis Willsch and Madita Willsch and Naoki Yoshioka and Nobuyasu Ito and Shengjun Yuan and Kristel Michielsen},
|
|
title = {Massively parallel quantum computer simulator, eleven years later},
|
|
journal = {Computer Physics Communications}
|
|
}
|
|
|
|
@book{DeRaedt2006,
|
|
title = {Handbook of Theoretical and Computational Nanotechnology},
|
|
author = {H. De Raedt and K. Michielsen},
|
|
editor = {M. Rieth and W. Schommers},
|
|
publisher = {American Scientific Publishers},
|
|
year = {2006},
|
|
pages = {2--48}
|
|
}
|
|
|
|
@unpublished{Smelyanskiy2016,
|
|
title = {qHiPSTER: The Quantum High Performance Software Testing Environment},
|
|
author = {Smelyanskiy, Mikhail and Sawaya, Nicolas P. D. and Aspuru-Guzik, Alán},
|
|
year = {2016},
|
|
eprint = {1601.07195},
|
|
archiveprefix = {arXiv},
|
|
primaryclass = {quant-ph},
|
|
note = {Unpublished},
|
|
keywords = {Quantum Physics (quant-ph), Distributed, Parallel, and Cluster Computing (cs.DC), FOS: Physical sciences, FOS: Physical sciences, FOS: Computer and information sciences, FOS: Computer and information sciences}
|
|
}
|
|
|
|
@article{Niwa2002,
|
|
doi = {10.1103/physreva.66.062317},
|
|
url = {https://doi.org/10.1103/physreva.66.062317},
|
|
year = {2002},
|
|
month = dec,
|
|
publisher = {American Physical Society ({APS})},
|
|
volume = {66},
|
|
number = {6},
|
|
author = {Jumpei Niwa and Keiji Matsumoto and Hiroshi Imai},
|
|
title = {General-purpose parallel simulator for quantum computing},
|
|
journal = {Physical Review A}
|
|
}
|
|
|
|
@article{Jones2019,
|
|
doi = {10.1038/s41598-019-47174-9},
|
|
url = {https://doi.org/10.1038/s41598-019-47174-9},
|
|
year = {2019},
|
|
month = jul,
|
|
publisher = {Springer Science and Business Media {LLC}},
|
|
volume = {9},
|
|
number = {1},
|
|
author = {Tyson Jones and Anna Brown and Ian Bush and Simon C. Benjamin},
|
|
title = {{QuEST} and High Performance Simulation of Quantum Computers},
|
|
journal = {Scientific Reports}
|
|
}
|
|
|
|
@inproceedings{Haner2016,
|
|
doi = {10.1109/sc.2016.73},
|
|
url = {https://doi.org/10.1109/sc.2016.73},
|
|
year = {2016},
|
|
month = nov,
|
|
publisher = {{IEEE}},
|
|
author = {Thomas Haner and Damian S. Steiger and Mikhail Smelyanskiy and Matthias Troyer},
|
|
title = {High Performance Emulation of Quantum Circuits},
|
|
booktitle = {{SC}16: International Conference for High Performance Computing, Networking, Storage and Analysis}
|
|
}
|
|
|
|
@article{Xiao2023,
|
|
doi = {10.1145/3604606},
|
|
url = {https://doi.org/10.1145/3604606},
|
|
year = {2023},
|
|
month = jun,
|
|
publisher = {Association for Computing Machinery ({ACM})},
|
|
author = {Guoqing Xiao and Chuanghui Yin and Tao Zhou and Xueqi Li and Yuedan Chen and Kenli Li},
|
|
title = {A Survey of Accelerating Parallel Sparse Linear Algebra},
|
|
journal = {{ACM} Computing Surveys}
|
|
}
|
|
|
|
@article{Bernstein1997,
|
|
doi = {10.1137/s0097539796300921},
|
|
url = {https://doi.org/10.1137/s0097539796300921},
|
|
year = {1997},
|
|
month = oct,
|
|
publisher = {Society for Industrial {\&} Applied Mathematics ({SIAM})},
|
|
volume = {26},
|
|
number = {5},
|
|
pages = {1411--1473},
|
|
author = {Ethan Bernstein and Umesh Vazirani},
|
|
title = {Quantum Complexity Theory},
|
|
journal = {{SIAM} Journal on Computing}
|
|
}
|
|
|
|
@unpublished{Boixo2017,
|
|
author = {Sergio Boixo and Sergei V. Isakov and Vadim N. Smelyanskiy and Hartmut Neven},
|
|
note = {Unpublished},
|
|
title = {Simulation of low-depth quantum circuits as complex undirected graphical models},
|
|
year = {2017},
|
|
archiveprefix = {arXiv},
|
|
primaryclass = {quant-ph},
|
|
eprint = {1712.05384}
|
|
}
|
|
|
|
@inproceedings{Burgholzer2021,
|
|
doi = {10.1109/qce52317.2021.00037},
|
|
url = {https://doi.org/10.1109/qce52317.2021.00037},
|
|
year = {2021},
|
|
month = oct,
|
|
publisher = {{IEEE}},
|
|
author = {Lukas Burgholzer and Hartwig Bauer and Robert Wille},
|
|
title = {Hybrid Schr\"{o}dinger-Feynman Simulation of Quantum Circuits With Decision Diagrams},
|
|
booktitle = {2021 {IEEE} International Conference on Quantum Computing and Engineering ({QCE})}
|
|
}
|
|
|
|
@inproceedings{Fatima2021,
|
|
doi = {10.1109/hpca51647.2021.00026},
|
|
url = {https://doi.org/10.1109/hpca51647.2021.00026},
|
|
year = {2021},
|
|
month = feb,
|
|
publisher = {{IEEE}},
|
|
author = {Aneeqa Fatima and Igor L. Markov},
|
|
title = {Faster Schr\"{o}dinger-style simulation of quantum circuits},
|
|
booktitle = {2021 {IEEE} International Symposium on High-Performance Computer Architecture ({HPCA})}
|
|
}
|
|
|
|
@article{Chen2018,
|
|
doi = {10.1016/j.scib.2018.06.007},
|
|
url = {https://doi.org/10.1016/j.scib.2018.06.007},
|
|
year = {2018},
|
|
month = aug,
|
|
publisher = {Elsevier {BV}},
|
|
volume = {63},
|
|
number = {15},
|
|
pages = {964--971},
|
|
author = {Zhao-Yun Chen and Qi Zhou and Cheng Xue and Xia Yang and Guang-Can Guo and Guo-Ping Guo},
|
|
title = {64-qubit quantum circuit simulation},
|
|
journal = {Science Bulletin}
|
|
}
|
|
|
|
@article{Kim2023,
|
|
doi = {10.1038/s41586-023-06096-3},
|
|
url = {https://doi.org/10.1038/s41586-023-06096-3},
|
|
year = {2023},
|
|
month = jun,
|
|
publisher = {Springer Science and Business Media {LLC}},
|
|
volume = {618},
|
|
number = {7965},
|
|
pages = {500--505},
|
|
author = {Youngseok Kim and Andrew Eddins and Sajant Anand and Ken Xuan Wei and Ewout van den Berg and Sami Rosenblatt and Hasan Nayfeh and Yantao Wu and Michael Zaletel and Kristan Temme and Abhinav Kandala},
|
|
title = {Evidence for the utility of quantum computing before fault tolerance},
|
|
journal = {Nature}
|
|
}
|
|
|
|
@article{Saffman2010,
|
|
doi = {10.1103/revmodphys.82.2313},
|
|
url = {https://doi.org/10.1103/revmodphys.82.2313},
|
|
year = {2010},
|
|
month = aug,
|
|
publisher = {American Physical Society ({APS})},
|
|
volume = {82},
|
|
number = {3},
|
|
pages = {2313--2363},
|
|
author = {M. Saffman and T. G. Walker and K. M{\o}lmer},
|
|
title = {Quantum information with Rydberg atoms},
|
|
journal = {Reviews of Modern Physics}
|
|
}
|
|
|
|
@unpublished{Li2018,
|
|
author = {Riling Li and Bujiao Wu and Mingsheng Ying and Xiaoming Sun and Guangwen Yang},
|
|
note = {Unpublished},
|
|
title = {Quantum Supremacy Circuit Simulation on Sunway TaihuLight},
|
|
year = {2018},
|
|
archiveprefix = {arXiv},
|
|
primaryclass = {quant-ph},
|
|
eprint = {1804.04797}
|
|
}
|
|
|
|
@article{Vidal2003,
|
|
doi = {10.1103/physrevlett.91.147902},
|
|
url = {https://doi.org/10.1103/physrevlett.91.147902},
|
|
year = {2003},
|
|
month = oct,
|
|
publisher = {American Physical Society ({APS})},
|
|
volume = {91},
|
|
number = {14},
|
|
author = {Guifr{\'{e}} Vidal},
|
|
title = {Efficient Classical Simulation of Slightly Entangled Quantum Computations},
|
|
journal = {Physical Review Letters}
|
|
}
|
|
|
|
@article{Markov2008,
|
|
doi = {10.1137/050644756},
|
|
url = {https://doi.org/10.1137/050644756},
|
|
year = {2008},
|
|
month = jan,
|
|
publisher = {Society for Industrial {\&} Applied Mathematics ({SIAM})},
|
|
volume = {38},
|
|
number = {3},
|
|
pages = {963--981},
|
|
author = {Igor L. Markov and Yaoyun Shi},
|
|
title = {Simulating Quantum Computation by Contracting Tensor Networks},
|
|
journal = {{SIAM} Journal on Computing}
|
|
}
|
|
|
|
@unpublished{Pednault2020,
|
|
author = {Edwin Pednault and John A. Gunnels and Giacomo Nannicini and Lior Horesh and Thomas Magerlein and Edgar Solomonik and Erik W. Draeger and Eric T. Holland and Robert Wisnieff},
|
|
note = {Unpublished},
|
|
title = {Pareto-Efficient Quantum Circuit Simulation Using Tensor Contraction Deferral},
|
|
year = {2020},
|
|
archiveprefix = {arXiv},
|
|
primaryclass = {quant-ph},
|
|
eprint = {1710.05867v4}
|
|
}
|
|
|
|
@book{Joshi1995,
|
|
title = {Matrices and Tensors in Physics},
|
|
author = {Joshi, A.W.},
|
|
isbn = {9788122405637},
|
|
lccn = {94021798},
|
|
url = {https://books.google.co.ck/books?id=FesDylvUy00C},
|
|
year = {1995},
|
|
publisher = {Wiley}
|
|
}
|
|
|
|
|
|
@article{DeLathauwer2000,
|
|
doi = {10.1137/s0895479896305696},
|
|
url = {https://doi.org/10.1137/s0895479896305696},
|
|
year = {2000},
|
|
month = jan,
|
|
publisher = {Society for Industrial {\&} Applied Mathematics ({SIAM})},
|
|
volume = {21},
|
|
number = {4},
|
|
pages = {1253--1278},
|
|
author = {Lieven De Lathauwer and Bart De Moor and Joos Vandewalle},
|
|
title = {A Multilinear Singular Value Decomposition},
|
|
journal = {{SIAM} Journal on Matrix Analysis and Applications}
|
|
}
|
|
|
|
@incollection{Vasilescu2002,
|
|
doi = {10.1007/3-540-47969-4_30},
|
|
url = {https://doi.org/10.1007/3-540-47969-4_30},
|
|
year = {2002},
|
|
publisher = {Springer Berlin Heidelberg},
|
|
pages = {447--460},
|
|
author = {M. Alex O. Vasilescu and Demetri Terzopoulos},
|
|
title = {Multilinear Analysis of Image Ensembles: {TensorFaces}},
|
|
booktitle = {Computer Vision {\textemdash} {ECCV} 2002}
|
|
}
|
|
|
|
@article{Kolda2009,
|
|
doi = {10.1137/07070111x},
|
|
url = {https://doi.org/10.1137/07070111x},
|
|
year = {2009},
|
|
month = aug,
|
|
publisher = {Society for Industrial {\&} Applied Mathematics ({SIAM})},
|
|
volume = {51},
|
|
number = {3},
|
|
pages = {455--500},
|
|
author = {Tamara G. Kolda and Brett W. Bader},
|
|
title = {Tensor Decompositions and Applications},
|
|
journal = {{SIAM} Review}
|
|
}
|
|
|
|
@article{Villalonga2019,
|
|
doi = {10.1038/s41534-019-0196-1},
|
|
url = {https://doi.org/10.1038/s41534-019-0196-1},
|
|
year = {2019},
|
|
month = oct,
|
|
publisher = {Springer Science and Business Media {LLC}},
|
|
volume = {5},
|
|
number = {1},
|
|
author = {Benjamin Villalonga and Sergio Boixo and Bron Nelson and Christopher Henze and Eleanor Rieffel and Rupak Biswas and Salvatore Mandr{\`{a}}},
|
|
title = {A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware},
|
|
journal = {npj Quantum Information}
|
|
}
|
|
|
|
@article{Guo2019,
|
|
doi = {10.1103/physrevlett.123.190501},
|
|
url = {https://doi.org/10.1103/physrevlett.123.190501},
|
|
year = {2019},
|
|
month = nov,
|
|
publisher = {American Physical Society ({APS})},
|
|
volume = {123},
|
|
number = {19},
|
|
author = {Chu Guo and Yong Liu and Min Xiong and Shichuan Xue and Xiang Fu and Anqi Huang and Xiaogang Qiang and Ping Xu and Junhua Liu and Shenggen Zheng and He-Liang Huang and Mingtang Deng and Dario Poletti and Wan-Su Bao and Junjie Wu},
|
|
title = {General-Purpose Quantum Circuit Simulator with Projected Entangled-Pair States and the Quantum Supremacy Frontier},
|
|
journal = {Physical Review Letters}
|
|
}
|
|
|
|
@article{McCaskey2018,
|
|
doi = {10.1371/journal.pone.0206704},
|
|
url = {https://doi.org/10.1371/journal.pone.0206704},
|
|
year = {2018},
|
|
month = dec,
|
|
publisher = {Public Library of Science ({PLoS})},
|
|
volume = {13},
|
|
number = {12},
|
|
pages = {e0206704},
|
|
author = {Alexander McCaskey and Eugene Dumitrescu and Mengsu Chen and Dmitry Lyakh and Travis Humble},
|
|
editor = {Nicholas Chancellor},
|
|
title = {Validating quantum-classical programming models with tensor network simulations},
|
|
journal = {{PLOS} {ONE}}
|
|
}
|
|
|
|
@article{Valiant2002,
|
|
doi = {10.1137/s0097539700377025},
|
|
url = {https://doi.org/10.1137/s0097539700377025},
|
|
year = {2002},
|
|
month = jan,
|
|
publisher = {Society for Industrial {\&} Applied Mathematics ({SIAM})},
|
|
volume = {31},
|
|
number = {4},
|
|
pages = {1229--1254},
|
|
author = {Leslie G. Valiant},
|
|
title = {Quantum Circuits That Can Be Simulated Classically in Polynomial Time},
|
|
journal = {{SIAM} Journal on Computing}
|
|
}
|
|
|
|
@article{Jozsa2008,
|
|
doi = {10.1098/rspa.2008.0189},
|
|
url = {https://doi.org/10.1098/rspa.2008.0189},
|
|
year = {2008},
|
|
month = jul,
|
|
publisher = {The Royal Society},
|
|
volume = {464},
|
|
number = {2100},
|
|
pages = {3089--3106},
|
|
author = {Richard Jozsa and Akimasa Miyake},
|
|
title = {Matchgates and classical simulation of quantum circuits},
|
|
journal = {Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences}
|
|
}
|
|
|
|
@article{Brod2016,
|
|
doi = {10.1103/physreva.93.062332},
|
|
url = {https://doi.org/10.1103/physreva.93.062332},
|
|
year = {2016},
|
|
month = jun,
|
|
publisher = {American Physical Society ({APS})},
|
|
volume = {93},
|
|
number = {6},
|
|
author = {Daniel J. Brod},
|
|
title = {Efficient classical simulation of matchgate circuits with generalized inputs and measurements},
|
|
journal = {Physical Review A}
|
|
}
|
|
|
|
@inproceedings{Lykov2022,
|
|
doi = {10.1109/qce53715.2022.00081},
|
|
url = {https://doi.org/10.1109/qce53715.2022.00081},
|
|
year = {2022},
|
|
month = sep,
|
|
publisher = {{IEEE}},
|
|
author = {Danylo Lykov and Roman Schutski and Alexey Galda and Valeri Vinokur and Yuri Alexeev},
|
|
title = {Tensor Network Quantum Simulator With Step-Dependent Parallelization},
|
|
booktitle = {2022 {IEEE} International Conference on Quantum Computing and Engineering ({QCE})}
|
|
}
|
|
|
|
@article{Gray2021,
|
|
doi = {10.22331/q-2021-03-15-410},
|
|
url = {https://doi.org/10.22331/q-2021-03-15-410},
|
|
year = {2021},
|
|
month = mar,
|
|
publisher = {Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften},
|
|
volume = {5},
|
|
pages = {410},
|
|
author = {Johnnie Gray and Stefanos Kourtis},
|
|
title = {Hyper-optimized tensor network contraction},
|
|
journal = {Quantum}
|
|
}
|
|
|
|
@article{Fried2018,
|
|
doi = {10.1371/journal.pone.0208510},
|
|
url = {https://doi.org/10.1371/journal.pone.0208510},
|
|
year = {2018},
|
|
month = dec,
|
|
publisher = {Public Library of Science ({PLoS})},
|
|
volume = {13},
|
|
number = {12},
|
|
pages = {e0208510},
|
|
author = {E. Schuyler Fried and Nicolas P. D. Sawaya and Yudong Cao and Ian D. Kivlichan and Jhonathan Romero and Al{\'{a}}n Aspuru-Guzik},
|
|
editor = {Itay Hen},
|
|
title = {{qTorch}: The quantum tensor contraction handler},
|
|
journal = {{PLOS} {ONE}}
|
|
}
|
|
|
|
@article{Schindler2020,
|
|
doi = {10.1088/2632-2153/ab94c5},
|
|
url = {https://doi.org/10.1088/2632-2153/ab94c5},
|
|
year = {2020},
|
|
month = jul,
|
|
publisher = {{IOP} Publishing},
|
|
volume = {1},
|
|
number = {3},
|
|
pages = {035001},
|
|
author = {Frank Schindler and Adam S Jermyn},
|
|
title = {Algorithms for tensor network contraction ordering},
|
|
journal = {Machine Learning: Science and Technology}
|
|
}
|
|
|
|
@inproceedings{Ibrahim2022,
|
|
author = {Ibrahim, Cameron and Lykov, Danylo and He, Zichang and Alexeev, Yuri and Safro, Ilya},
|
|
booktitle = {2022 IEEE High Performance Extreme Computing Conference (HPEC)},
|
|
title = {Constructing Optimal Contraction Trees for Tensor Network Quantum Circuit Simulation},
|
|
year = {2022},
|
|
volume = {},
|
|
number = {},
|
|
pages = {1-8},
|
|
doi = {10.1109/HPEC55821.2022.9926353}
|
|
}
|
|
|
|
@article{Pfeifer2014,
|
|
doi = {10.1103/physreve.90.033315},
|
|
url = {https://doi.org/10.1103/physreve.90.033315},
|
|
year = {2014},
|
|
month = sep,
|
|
publisher = {American Physical Society ({APS})},
|
|
volume = {90},
|
|
number = {3},
|
|
author = {Robert N. C. Pfeifer and Jutho Haegeman and Frank Verstraete},
|
|
title = {Faster identification of optimal contraction sequences for tensor networks},
|
|
journal = {Physical Review E}
|
|
}
|
|
|
|
|
|
@article{Liang2021,
|
|
author = {Liang, Ling and Xu, Jianyu and Deng, Lei and Yan, Mingyu and Hu, Xing and Zhang, Zheng and Li, Guoqi and Xie, Yuan},
|
|
journal = {IEEE Journal of Selected Topics in Signal Processing},
|
|
title = {Fast Search of the Optimal Contraction Sequence in Tensor Networks},
|
|
year = {2021},
|
|
volume = {15},
|
|
number = {3},
|
|
pages = {574-586},
|
|
doi = {10.1109/JSTSP.2021.3051231}
|
|
}
|
|
|
|
@article{Pan2022,
|
|
doi = {10.1103/physrevlett.128.030501},
|
|
url = {https://doi.org/10.1103/physrevlett.128.030501},
|
|
year = {2022},
|
|
month = jan,
|
|
publisher = {American Physical Society ({APS})},
|
|
volume = {128},
|
|
number = {3},
|
|
author = {Feng Pan and Pan Zhang},
|
|
title = {Simulation of Quantum Circuits Using the Big-Batch Tensor Network Method},
|
|
journal = {Physical Review Letters}
|
|
}
|
|
|
|
@unpublished{Tindall2023,
|
|
author = {Joseph Tindall and Matt Fishman and Miles Stoudenmire and Dries Sels},
|
|
note = {Unpublished},
|
|
title = {Efficient tensor network simulation of IBM's kicked Ising experiment},
|
|
year = {2023},
|
|
archiveprefix = {arXiv},
|
|
primaryclass = {quant-ph},
|
|
eprint = {2306.14887}
|
|
}
|
|
|
|
@unpublished{Burgholzer2023,
|
|
author = {Lukas Burgholzer and Alexander Ploier and Robert Wille},
|
|
note = {Unpublished},
|
|
title = {Tensor Networks or Decision Diagrams? Guidelines for Classical Quantum Circuit Simulation},
|
|
year = {2023},
|
|
archiveprefix = {arXiv},
|
|
primaryclass = {quant-ph},
|
|
eprint = {2302.06616}
|
|
}
|
|
|
|
@article{Niemann2016,
|
|
author = {Niemann, Philipp and Wille, Robert and Miller, David Michael and Thornton, Mitchell A. and Drechsler, Rolf},
|
|
journal = {IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems},
|
|
title = {QMDDs: Efficient Quantum Function Representation and Manipulation},
|
|
year = {2016},
|
|
volume = {35},
|
|
number = {1},
|
|
pages = {86-99},
|
|
doi = {10.1109/TCAD.2015.2459034}
|
|
}
|
|
|
|
@article{Lu2011,
|
|
author = {Lu, Chin-Yung and Wang, Shiou-An and Kuo, Sy-Yen},
|
|
journal = {IEEE Transactions on Computers},
|
|
title = {An Extended XQDD Representation for Multiple-Valued Quantum Logic},
|
|
year = {2011},
|
|
volume = {60},
|
|
number = {10},
|
|
pages = {1377-1389},
|
|
doi = {10.1109/TC.2011.114}
|
|
}
|
|
|
|
@inproceedings{Zulehner2019efficiently,
|
|
author = {Zulehner, Alwin and Hillmich, Stefan and Wille, Robert},
|
|
booktitle = {2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)},
|
|
title = {How to Efficiently Handle Complex Values? Implementing Decision Diagrams for Quantum Computing},
|
|
year = {2019},
|
|
volume = {},
|
|
number = {},
|
|
pages = {1-7},
|
|
doi = {10.1109/ICCAD45719.2019.8942057}
|
|
}
|
|
|
|
@inproceedings{Viamontes2004,
|
|
author = {Viamontes, G.F. and Markov, I.L. and Hayes, J.P.},
|
|
booktitle = {Proceedings Design, Automation and Test in Europe Conference and Exhibition},
|
|
title = {High-performance QuIDD-based simulation of quantum circuits},
|
|
year = {2004},
|
|
volume = {2},
|
|
number = {},
|
|
pages = {1354-1355 Vol.2},
|
|
doi = {10.1109/DATE.2004.1269084}
|
|
}
|
|
|
|
@inproceedings{Zulehner2019matrix,
|
|
author = {Zulehner, Alwin and Wille, Robert},
|
|
booktitle = {2019 Design, Automation {\&} Test in Europe Conference {\&} Exhibition (DATE)},
|
|
title = {Matrix-Vector vs. Matrix-Matrix Multiplication: Potential in DD-based Simulation of Quantum Computations},
|
|
year = {2019},
|
|
volume = {},
|
|
number = {},
|
|
pages = {90-95},
|
|
doi = {10.23919/DATE.2019.8714836}
|
|
}
|
|
|
|
@article{Burgholzer2021equivalence,
|
|
author = {Burgholzer, Lukas and Wille, Robert},
|
|
journal = {IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems},
|
|
title = {Advanced Equivalence Checking for Quantum Circuits},
|
|
year = {2021},
|
|
volume = {40},
|
|
number = {9},
|
|
pages = {1810-1824},
|
|
doi = {10.1109/TCAD.2020.3032630}
|
|
}
|
|
|
|
@article{Preskill2018,
|
|
doi = {10.22331/q-2018-08-06-79},
|
|
url = {https://doi.org/10.22331/q-2018-08-06-79},
|
|
year = {2018},
|
|
month = aug,
|
|
publisher = {Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften},
|
|
volume = {2},
|
|
pages = {79},
|
|
author = {John Preskill},
|
|
title = {Quantum Computing in the {NISQ} era and beyond},
|
|
journal = {Quantum}
|
|
}
|
|
|
|
@book{Breuer2002,
|
|
title = {The Theory of Open Quantum Systems},
|
|
author = {Breuer, H.P. and Petruccione, F.},
|
|
isbn = {9780198520634},
|
|
lccn = {2002075713},
|
|
url = {https://books.google.pt/books?id=0Yx5VzaMYm8C},
|
|
year = {2002},
|
|
publisher = {Oxford University Press}
|
|
}
|
|
|
|
@article{Bassi2008,
|
|
doi = {10.1103/physreva.77.032323},
|
|
url = {https://doi.org/10.1103/physreva.77.032323},
|
|
year = {2008},
|
|
month = mar,
|
|
publisher = {American Physical Society ({APS})},
|
|
volume = {77},
|
|
number = {3},
|
|
author = {Angelo Bassi and Dirk-Andr{\'{e}} Deckert},
|
|
title = {Noise gates for decoherent quantum circuits},
|
|
journal = {Physical Review A}
|
|
}
|
|
|
|
@software{cirq2022,
|
|
author = {{Cirq Developers}},
|
|
title = {Cirq},
|
|
month = dec,
|
|
year = 2022,
|
|
note = {{See full list of authors on Github: https://github
|
|
.com/quantumlib/Cirq/graphs/contributors}},
|
|
publisher = {Zenodo},
|
|
version = {v1.1.0},
|
|
doi = {10.5281/zenodo.7465577},
|
|
url = {https://doi.org/10.5281/zenodo.7465577}
|
|
}
|
|
|
|
@manual{cirq2022simulator,
|
|
author = {{Cirq Developers}},
|
|
title = {cirq.Simulator},
|
|
year = {2023},
|
|
month = {06},
|
|
note = {\url{https://quantumai.google/reference/python/cirq/Simulator}}
|
|
}
|
|
|
|
@software{qsim2020,
|
|
author = {{Quantum AI team} and collaborators},
|
|
title = {qsim, qsimh},
|
|
month = Sep,
|
|
year = 2020,
|
|
publisher = {Zenodo},
|
|
doi = {10.5281/zenodo.4023103},
|
|
url = {https://doi.org/10.5281/zenodo.4023103}
|
|
}
|
|
|
|
@article{numpy2020,
|
|
title = {Array programming with {NumPy}},
|
|
author = {Charles R. Harris and K. Jarrod Millman and St{\'{e}}fan J.
|
|
van der Walt and Ralf Gommers and Pauli Virtanen and David
|
|
Cournapeau and Eric Wieser and Julian Taylor and Sebastian
|
|
Berg and Nathaniel J. Smith and Robert Kern and Matti Picus
|
|
and Stephan Hoyer and Marten H. van Kerkwijk and Matthew
|
|
Brett and Allan Haldane and Jaime Fern{\'{a}}ndez del
|
|
R{\'{i}}o and Mark Wiebe and Pearu Peterson and Pierre
|
|
G{\'{e}}rard-Marchant and Kevin Sheppard and Tyler Reddy and
|
|
Warren Weckesser and Hameer Abbasi and Christoph Gohlke and
|
|
Travis E. Oliphant},
|
|
year = {2020},
|
|
month = sep,
|
|
journal = {Nature},
|
|
volume = {585},
|
|
number = {7825},
|
|
pages = {357--362},
|
|
doi = {10.1038/s41586-020-2649-2},
|
|
publisher = {Springer Science and Business Media {LLC}},
|
|
url = {https://doi.org/10.1038/s41586-020-2649-2}
|
|
}
|
|
|
|
@manual{microsoft2023,
|
|
author = {Microsoft},
|
|
title = {What are {Q\#} and the Quantum Development Kit?},
|
|
year = {2023},
|
|
url = {https://learn.microsoft.com/en-gb/azure/quantum/overview-what-is-qsharp-and-qdk},
|
|
urldate = {\today},
|
|
note = {\url{https://learn.microsoft.com/en-gb/azure/quantum/overview-what-is-qsharp-and-qdk}},
|
|
} |