Fetching the paper…
Reading the bibliography…
A defining feature in the field of quantum computing is the potential of a quantum device to outperform its classical counterpart for a specific computational task.
J. Edmonds, E. L., Math. Program 5
1973
Earlier work this paper cites.
P. W. Shor, in Proceedings 35th annual symposium on foundations of computer science (Ieee, 1994) pp. 124–134
1994
Earlier work this paper cites.
L. K. Grover, arXiv preprint quant-ph/9605043 (1996)
1996
Earlier work this paper cites.
A. R. Calderbank and P. W. Shor, Physical Review A 54
1996
Earlier work this paper cites.
A. Steane, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 452
1996
Earlier work this paper cites.
D. Gottesman, arXiv preprint quant-ph/9705052 (1997)
1997
Earlier work this paper cites.
S. B. Bravyi and A. Y. Kitaev, arXiv preprint quant-ph/9811052 (1998)
1998
Earlier work this paper cites.
M. A. Nielsen and I. L. Chuang, “Quantum computation and quantum information,” (2000)
2000
Earlier work this paper cites.
Since quantum speedup is usually defined with respect to quantum devices using polynomial quantum resources Nielsen and Chuang 2000
2000
Earlier work this paper cites.
2001
Earlier work this paper cites.
R. Raussendorf and H. J. Briegel, Physical Review Letters 86
2001
Earlier work this paper cites.
This is usually the input part of an MBQC Raussendorf and Briegel 2001 , which is the basis of our construction
2001
Earlier work this paper cites.
E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Journal of Mathematical Physics 43
2002
Earlier work this paper cites.
R. Raussendorf, D. E. Browne, and H. J. Briegel, Physical review A 68
2003
Earlier work this paper cites.
J. Emerson, Y. S. Weinstein, M. Saraceno, S. Lloyd, and D. G. Cory, science 302
2003
Earlier work this paper cites.
A. Y. Kitaev, Annals of Physics 303
2003
Earlier work this paper cites.
P. Hayden, D. Leung, P. W. Shor, and A. Winter, Communications in Mathematical Physics 250
2004
Earlier work this paper cites.
P. Aliferis, D. Gottesman, and J. Preskill, arXiv preprint quant-ph/0504218 (2005)
2005
Earlier work this paper cites.
S. Bravyi and A. Kitaev, Physical Review A 71
2005
Earlier work this paper cites.
B. W. Reichardt, Quantum Information Processing 4
2005
Earlier work this paper cites.
M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Nest, and H.-J. Briegel, arXiv preprint quant-ph/0602096 (2006)
2006
Earlier work this paper cites.
R. Raussendorf, J. Harrington, and K. Goyal, Annals of physics 321
2006
Earlier work this paper cites.
P. Aliferis, D. Gottesman, and J. Preskill, arXiv preprint quant-ph/0703264 (2007)
2007
Earlier work this paper cites.
R. Raussendorf, J. Harrington, and K. Goyal, New Journal of Physics 9
2007
Earlier work this paper cites.
D. E. Browne, E. Kashefi, M. Mhalla, and S. Perdrix, New Journal of Physics 9
2007
Earlier work this paper cites.
P. Hayden and J. Preskill, Journal of high energy physics 2007
2007
Earlier work this paper cites.
A. G. Fowler and K. Goyal, arXiv preprint arXiv:0805.3202 (2008)
2008
Earlier work this paper cites.
A. Broadbent, J. Fitzsimons, and E. Kashefi, in 2009 50th Annual IEEE Symposium on Foundations of Computer Science (IEEE, 2009) pp. 517–526
2009
Earlier work this paper cites.
C. Dankert, R. Cleve, J. Emerson, and E. Livine, Physical Review A 80
2009
Earlier work this paper cites.
D. Browne, E. Kashefi, and S. Perdrix, in Conference on Quantum Computation, Communication, and Cryptography (Springer, 2010) pp. 35–46
2010
Earlier work this paper cites.
M. J. Bremner, R. Jozsa, and D. J. Shepherd, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467
2011
Earlier work this paper cites.
S. Aaronson and A. Arkhipov, in Proceedings of the forty-third annual ACM symposium on Theory of computing (ACM, 2011) pp. 333–342
2011
Cited alongside, same era.
A. J. Landahl, J. T. Anderson, and P. R. Rice, arXiv preprint arXiv:1108.5738 (2011)
2011
Cited alongside, same era.
D. S. Wang, A. G. Fowler, and L. C. Hollenberg, Physical Review A 83
2011
Cited alongside, same era.
A. G. Fowler, Physical review letters 109
2012
Cited alongside, same era.
W. I. Gasarch, ACM SIGACT News 43
2012
Cited alongside, same era.
S. Bravyi and J. Haah, Physical Review A 86
2012
Cited alongside, same era.
D. Hangleiter, J. Bermejo-Vega, M. Schwarz, and J. Eisert, Quantum 2
2018
Later among the works it cites.
S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Nature Physics 14
2018
Later among the works it cites.
C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, S. V. Isakov, V. Smelyanskiy, A. Megrant, B. Chiaro, A. Dunsworth, K. Arya, et al. , Science 360
2018
Later among the works it cites.
S. Bravyi, D. Gosset, and R. Koenig, Science 362
2018
Later among the works it cites.
M. Oszmaniec and D. J. Brod, New Journal of Physics 20
2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2013
Cited alongside, same era.
C. Jones, Physical Review A 87
2013
Cited alongside, same era.
Y. Li, New Journal of Physics 17
2015
Cited alongside, same era.
The constant depth procedure of Li 2015 also requires some post-selection (in the presence of noise). However, this post-selection is usually over measurement results of a small (constant) number of qubits, and the success probability is also a constant Li 2015 . We can therefore implement in paralell O ( 1 ) O(1) runs of this constant depth procedure, and we are guaranteed with high probability that at least one run corresponds to the desired post-selection
2015
Cited alongside, same era.
Although the noise model used in Li 2015 is not the same as the one we use here, where in Li 2015 they use independent depolarizing noise for preparations and gate application, and with different rates for single and two-qubit gates, we believe their results hold in our case as well. Indeed, viewing a local stochastic noise with rate p p on a single qubit, this qubit could experience an error (after preparation, measurement or gate application) with probability p r ≤ p pr\leq p (from the definition of local stochastic noise with | F | = 1 |F|=1 , see main text), this is in line with the noise model of Li 2015 where the probability of error is exactly p p . Furthermore, choosing different error rates for local stochastic noise applied after single and two-qubit gates allows mimicking what happens in the noise model of Li 2015
2015
Cited alongside, same era.
This is guaranteed by using the technique of Li 2015 if the error rate of preparations, single and two-qubit gates is low enough. Since ε \varepsilon in Li 2015 is generally a function of these error rates
2015
Cited alongside, same era.
2018
Later among the works it cites.
O. Fawzi, A. Grospellier, and A. Leverrier, in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2018) pp. 743–754
2018
Later among the works it cites.
R. Mezher, J. Ghalbouni, J. Dgheim, and D. Markham, Physical Review A 97
2018
Later among the works it cites.
A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, arXiv preprint arXiv:1803.04402 (2018)
2018
Later among the works it cites.
M. B. Hastings and J. Haah, Physical review letters 120
2018
Later among the works it cites.
J. Haah and M. B. Hastings, Quantum 2
2018
Later among the works it cites.
O. Fawzi, A. Grospellier, and A. Leverrier, in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2018) pp. 743–754
2018
Later among the works it cites.
R. Mezher, J. Ghalbouni, J. Dgheim, and D. Markham, arXiv preprint arXiv:1905.01504 (2019)
2019
Later among the works it cites.
F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al. , Nature 574
2019
Later among the works it cites.
L. Novo, J. Bermejo-Vega, and R. García-Patrón, arXiv preprint arXiv:1912.06608 (2019)
2019
Later among the works it cites.
2019
Later among the works it cites.
S. Bravyi, D. Gosset, R. Koenig, and M. Tomamichel, arXiv preprint arXiv:1904.01502 (2019)
2019
Later among the works it cites.
2019
Later among the works it cites.
V. Shchesnovich, arXiv preprint arXiv:1902.02258 (2019)
2019
Later among the works it cites.
T. Kapourniotis and A. Datta, Quantum 3
2019
Later among the works it cites.
R. Movassagh, arXiv preprint arXiv:1909.06210 (2019)
2019
Later among the works it cites.
A recent paper Napp et al. 2019 shows that the outputs of 2D constant depth circuits are generally efficiently simulable classically. However, we note that the circuits discussed here Bermejo-Vega et al. 2018 ; Gao et al. 2017 ; Hangleiter et al. 2018 ; Haferkamp et al. 2019 ; Mezher et al. 2018 ; Mezher et al. 2019 correspond to worst-case instances of the circuits in Napp et al. 2019 , where their efficient classical algorithm fails. Indeed, the X Y XY measurement angles performed effectively induce a 1D dynamics which is purely unitary, and which for the choice of X Y XY angles made in Mezher et al. 2018 ; Mezher et al. 2019 and here in our case typically evolves an input state onto a volume law entangled state. The classical algorithm in Napp et al. 2019 is generally inefficient in simulating such volume law entangled states
2019
Later among the works it cites.
One way to do this would be measuring the other logical qubit of the Bell state non-adaptively in Z ¯ \overline{Z} , then decoding the result and applying an X ¯ \overline{X} to the unmeasured logical qubit dependant on the decoded measurement result. This should be done after the recovery Pauli operator of Bravyi et al. 2019 has been applied. The noise acting on the unmeasured qubit after completion would still be local stochastic with constant rate. Indeed, after applying the recovery operator of Bravyi et al. 2019 , we are left with a Bell state with some local stochastic noise E E Bravyi et al. 2019 , then after measuring one logical qubit and decoding (which succeeds with high probability if error rates are small), we apply a conditional X ¯ \overline{X} operator to the unmeasured logical qubit. In the case this X ¯ \overline{X} is applied, it introduces also a local stochastic noise E ′ E^{{}^{\prime}} , but because X ¯ \overline{X} is a constant depth Clifford gate with only single qubit gates, E ′ E^{{}^{\prime}} can be merged with E E to give a single local stochastic noise E ′′ E^{{}^{\prime\prime}} which is still local stochastic with constant rate, by the likes of arguments of Equation ( 8
2019
Later among the works it cites.
C. Chamberland and A. W. Cross, Quantum 3
2019
Later among the works it cites.
Y. Takeuchi, A. Mantri, T. Morimae, A. Mizutani, and J. F. Fitzsimons, npj Quantum Information 5
2019
Later among the works it cites.
This assumption may seem strong, but it is actually very mild and has no effect on our end result. To see this, suppose we drop this assumption, then the probability of success of all k . n k.n decodings should now be calcuated by a union bound. From the properties of local stochastic noise (namely that local stochastic noise on a subset of qubits of the system is still local stochastic with the same rate Bravyi et al. 2019 ) a decoding of a logical qubit succeeds (is able to identify and correct for the error) with probability p s i n g l e = 1 − p f = 1 − e − O ( l ) p_{single}=1-p_{f}=1-e^{-O(\sqrt{l})} (when the error rates of all local stochastic noise in our construction are adequately low, i.e below the threshold of fault-tolerant computing with the surface code), therefore the probability that all k . n k.n decodings succeed is given by P = 1 − k . n + k . n . p s i n g l e = 1 − k . n . e − O ( l ) P=1-k.n+k.n.p_{single}=1-k.n.e^{-O(\sqrt{l})} , by a standard bound on the intersection of k . n k.n events derived from a union bound. The assumption we make in the main text results in a good approximation of P P , and is simpler to state (which is why we used it in the main text). Finally, note that this does not mean that errors between physical qubits of two entangled logical qubits are uncorrelated. Indeed, the correlation between these qubits is accounted for in the propagation rules of local stochastic noise Bravyi et al. 2019 , since forward propagating local stochastic noise in Clifford circuits composed of single and two-qubit gates generally results in local stochastic noise with higher error rate Bravyi et al. 2019
2019
Later among the works it cites.
Actually, it is something like 2 . k . n 2.k.n if we include decoding of measured logical qubits of the Bell states obtained at the end of the single shot procedure of Bravyi et al. 2019 (see [ 57 ] [57] ). This changes nothing in the analysis we have done, so we chose to omit it in the main text for simplicity
2019
Later among the works it cites.
2019
Later among the works it cites.
K. Noh, L. Jiang, and B. Fefferman, arXiv preprint arXiv:2003.13163 (2020)
2020
Closest in time.
C. Chamberland and K. Noh, arXiv preprint arXiv:2003.03049 (2020)
2020
Closest in time.
D. Markham and A. Krause, Cryptography 4
2020
Closest in time.