Hierarchies of resources for measurement-based quantum computation. (English) Zbl 1510.81014
Summary: For certain restricted computational tasks, quantum mechanics provides a provable advantage over any possible classical implementation. Several of these results have been proven using the framework of measurement-based quantum computation (MBQC), where nonlocality and more generally contextuality have been identified as necessary resources for certain quantum computations. Here, we consider the computational power of MBQC in more detail by refining its resource requirements, both on the allowed operations and the number of accessible qubits. More precisely, we identify which Boolean functions can be computed in non-adaptive MBQC, with local operations contained within a finite level in the Clifford hierarchy. Moreover, for non-adaptive MBQC restricted to certain subtheories such as stabiliser MBQC, we compute the minimal number of qubits required to compute a given Boolean function. Our results point towards hierarchies of resources that more sharply characterise the power of MBQC beyond the binary of contextuality vs non-contextuality.
MSC:
| 81P15 | Quantum measurement theory, state operations, state preparations |
| 81P68 | Quantum computation |
| 68Q09 | Other nonclassical models of computation |
References:
| [1] | Raussendorf, R., Contextuality in measurement-based quantum computation, Phys. Rev. A, 88 (2013) · doi:10.1103/PhysRevA.88.022322 |
| [2] | Howard, M.; Wallman, J.; Veitch, V.; Emerson, J., Contextuality supplies the ‘magic’ for quantum computation, Nature, 510, 351-5 (2014) · doi:10.1038/nature13460 |
| [3] | Bermejo-Vega, J.; Delfosse, N.; Browne, D. E.; Okay, C.; Raussendorf, R., Contextuality as a resource for models of quantum computation with qubits, Phys. Rev. Lett., 119 (2017) · doi:10.1103/PhysRevLett.119.120505 |
| [4] | Delfosse, N.; Guerin, P. A.; Bian, J.; Raussendorf, R., Wigner function negativity and contextuality in quantum computation on rebits, Phys. Rev. X, 5 (2015) · doi:10.1103/PhysRevX.5.021003 |
| [5] | Raussendorf, R.; Browne, D. E.; Delfosse, N.; Okay, C.; Bermejo-Vega, J., Contextuality and Wigner function negativity in qubit quantum computation, Phys. Rev. A, 95 (2017) · doi:10.1103/PhysRevA.95.052334 |
| [6] | Karanjai, A.; Wallman, J. J.; Bartlett, S. D., Contextuality bounds the efficiency of classical simulation of quantum processes (2018) |
| [7] | Raussendorf, R., Cohomological framework for contextual quantum computations, Quantum Inf. Comput., 19, 1141-70 (2019) · doi:10.26421/QIC19.13-14-4 |
| [8] | Okay, C.; Roberts, S.; Bartlett, S.; Raussendorf, R., Topological proofs of contextuality in quantum mechanics, Quantum Inf. Comput., 17, 1135-66 (2017) · doi:10.26421/QIC17.13-14-5 |
| [9] | Veitch, V.; Mousavian, S. A H.; Gottesman, D.; Emerson, J., The resource theory of stabilizer quantum computation, New J. Phys., 16 (2014) · Zbl 1451.81184 · doi:10.1088/1367-2630/16/1/013009 |
| [10] | Mansfield, S.; Kashefi, E., Quantum advantage from sequential-transformation contextuality, Phys. Rev. Lett., 121 (2018) · doi:10.1103/PhysRevLett.121.230401 |
| [11] | Pashayan, H.; Wallman, J. J.; Bartlett, S. D., Estimating outcome probabilities of quantum circuits using quasiprobabilities, Phys. Rev. Lett., 115 (2015) · doi:10.1103/PhysRevLett.115.070501 |
| [12] | Nadish, de S., Logical paradoxes in quantum computation, pp 335-43 (2018), Association for Computing Machinery · Zbl 1452.81077 |
| [13] | Frembs, M.; Roberts, S.; Bartlett, S. D., Contextuality as a resource for measurement-based quantum computation beyond qubits, New J. Phys., 20 (2018) · doi:10.1088/1367-2630/aae3ad |
| [14] | Kochen, S.; Specker, E. P., The problem of hidden variables in quantum mechanics, J. Math. Mech., 17, 59-87 (1967) · Zbl 0156.23302 · doi:10.2307/24902153 |
| [15] | Bravyi, S.; Gosset, D.; König, R., Quantum advantage with shallow circuits, Science, 362, 308-11 (2018) · Zbl 1431.81042 · doi:10.1126/science.aar3106 |
| [16] | Bravyi, S.; Gosset, D.; Koenig, R.; Tomamichel, M., Quantum advantage with noisy shallow circuits, Nat. Phys., 16, 1040-5 (2020) · doi:10.1038/s41567-020-0948-z |
| [17] | Raussendorf, R.; Briegel, H. J., A one-way quantum computer, Phys. Rev. Lett., 86, 5188-91 (2001) · doi:10.1103/PhysRevLett.86.5188 |
| [18] | Raussendorf, R.; Browne, D. E.; Briegel, H. J., Measurement-based quantum computation on cluster states, Phys. Rev. A, 68 (2003) · doi:10.1103/PhysRevA.68.022312 |
| [19] | Briegel, H. J.; Browne, D. E.; Dür, W.; Raussendorf, R.; Van den Nest, M., Measurement-based quantum computation, Nat. Phys., 5, 19-26 (2009) · doi:10.1038/nphys1157 |
| [20] | Anders, J.; Browne, D. E., Computational power of correlations, Phys. Rev. Lett., 102 (2009) · doi:10.1103/PhysRevLett.102.050502 |
| [21] | Raussendorf, R., Contextuality in measurement-based quantum computation, Phys. Rev. A, 88 (2013) · doi:10.1103/PhysRevA.88.022322 |
| [22] | Hoban, M. J.; Campbell, E. T.; Loukopoulos, K.; Browne, D. E., Non-adaptive measurement-based quantum computation and multi-party Bell inequalities, New J. Phys., 13 (2011) · Zbl 1448.81107 · doi:10.1088/1367-2630/13/2/023014 |
| [23] | Gottesman, D., The Heisenberg representation of quantum computers (1998) |
| [24] | Aaronson, S.; Gottesman, D., Improved simulation of stabilizer circuits, Phys. Rev. A, 70 (2004) · doi:10.1103/PhysRevA.70.052328 |
| [25] | Gross, D., Hudson’s theorem for finite-dimensional quantum systems, J. Math. Phys., 47 (2006) · Zbl 1112.81012 · doi:10.1063/1.2393152 |
| [26] | Amy, M.; Mosca, M., T-count optimization and Reed-Muller codes, IEEE Trans. Inf. Theory, 65, 4771-84 (2019) · Zbl 1432.94189 · doi:10.1109/TIT.2019.2906374 |
| [27] | Seroussi, G.; Lempel, A., Maximum likelihood decoding of certain Reed-Muller codes (Corresp.), IEEE Trans. Inf. Theory, 29, 448-50 (1983) · Zbl 0505.94026 · doi:10.1109/TIT.1983.1056662 |
| [28] | Heyfron, L. E.; Campbell, E. T., An efficient quantum compiler that reduces T count, Quantum Sci. Technol., 4 (2018) · doi:10.1088/2058-9565/aad604 |
| [29] | Kissinger, A.; van de Wetering, J., Reducing the number of non-Clifford gates in quantum circuits, Phys. Rev. A, 102 (2020) · doi:10.1103/PhysRevA.102.022406 |
| [30] | Heyfron, L. E.; Campbell, E., A quantum compiler for qudits of prime dimension greater than 3 (2019) |
| [31] | Werner, R. F.; Wolf, M. M., All-multipartite Bell-correlation inequalities for two dichotomic observables per site, Phys. Rev. A, 64 (2001) · doi:10.1103/PhysRevA.64.032112 |
| [32] | Abramsky, S.; Barbosa, R. S.; Carù, G.; de Silva, N.; Kishida, K.; Mansfield, S., Minimum quantum resources for strong non-locality, vol 73, pp 9:1-9:20 (2018), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik · Zbl 1427.81006 |
| [33] | Kolokotronis, N.; Limniotis, K.; Kalouptsidis, N., Best quadratic approximations of cubic Boolean functions, IACR Cryptol. ePrint Arch., 37, 2007 (2007) |
| [34] | Kolokotronis, N.; Limniotis, K.; Kalouptsidis, N., Best affine and quadratic approximations of particular classes of Boolean functions, IEEE Trans. Inf. Theory, 55, 5211-22 (2009) · Zbl 1367.94476 · doi:10.1109/TIT.2009.2030452 |
| [35] | Zeng, B.; Chen, X.; Chuang, I. L., Semi-Clifford operations, structure of Ck) hierarchy and gate complexity for fault-tolerant quantum computation, Phys. Rev. A, 77 (2008) · doi:10.1103/PhysRevA.77.042313 |
| [36] | Gross, D.; Nest, M., The LU-LC conjecture, diagonal local operations and quadratic forms over GF(2), Quantum Inf. Comput., 8, 263-81 (032008) · Zbl 1236.81066 · doi:10.26421/QIC8.3-4-3 |
| [37] | Cui, S. X.; Gottesman, D.; Krishna, A., Diagonal gates in the Clifford hierarchy, Phys. Rev. A, 95 (2017) · doi:10.1103/PhysRevA.95.012329 |
| [38] | de Silva, N., Efficient quantum gate teleportation in higher dimensions, Proc. R. Soc. A, 477 (2021) · doi:10.1098/rspa.2020.0865 |
| [39] | Lempel, A., Matrix factorization over GF(2) and trace-orthogonal bases of GF(2), SIAM J. Comput., 4, 175-86 (1975) · Zbl 0331.94006 · doi:10.1137/0204014 |
| [40] | Mori, R., Periodic Fourier representation of Boolean functions (2018) |
| [41] | O’Donnell, R., Analysis of Boolean Functions (2014), Cambridge: Cambridge University Press, Cambridge · Zbl 1336.94096 |
| [42] | Yoshida, B., Gapped boundaries, group cohomology and fault-tolerant logical gates, Ann. Phys., NY, 377, 387-413 (2017) · Zbl 1368.81065 · doi:10.1016/j.aop.2016.12.014 |
| [43] | Abramsky, S.; Brandenburger, A., The sheaf-theoretic structure of non-locality and contextuality, New J. Phys., 13 (2011) · Zbl 1448.81028 · doi:10.1088/1367-2630/13/11/113036 |
| [44] | Okay, C.; Tyhurst, E.; Raussendorf, R., The cohomological and the resource-theoretic perspective on quantum contextuality: common ground through the contextual fraction, Quantum Inf. Comput., 18, 1272-94 (2018) · doi:10.26421/QIC18.15-16-2 |
| [45] | Chen, X.; Gu, Z-C; Liu, Z-X; Wen, X-G, Symmetry protected topological orders and the group cohomology of their symmetry group, Phys. Rev. B, 87 (2013) · doi:10.1103/PhysRevB.87.155114 |
| [46] | Daniel, A. K.; Miyake, A., Quantum computational advantage with string order parameters of one-dimensional symmetry-protected topological order, Phys. Rev. Lett., 126 (2021) · doi:10.1103/PhysRevLett.126.090505 |
| [47] | Liu, Z-W; Winter, A., Many-body quantum magic (2020) |
| [48] | Ellison, T. D.; Kato, K.; Liu, Z-W; Hsieh, T. H., Symmetry-protected sign problem and magic in quantum phases of matter, Quantum, 5, 612 (2021) · doi:10.22331/q-2021-12-28-612 |
| [49] | Else, D. V.; Bartlett, S. D.; Doherty, A. C., Symmetry protection of measurement-based quantum computation in ground states, New J. Phys., 14 (2012) · Zbl 1448.81233 · doi:10.1088/1367-2630/14/11/113016 |
| [50] | Nautrup, H. P.; Wei, T-C, Symmetry-protected topologically ordered states for universal quantum computation, Phys. Rev. A, 92 (2015) · doi:10.1103/PhysRevA.92.052309 |
| [51] | Miller, J.; Miyake, A., Hierarchy of universal entanglement in 2D measurement-based quantum computation, npj Quantum Inf., 2 (2016) · doi:10.1038/npjqi.2016.36 |
| [52] | Raussendorf, R.; Okay, C.; Wang, D-S; Stephen, D. T.; Nautrup, H. P., Computationally universal phase of quantum matter, Phys. Rev. Lett., 122 (2019) · doi:10.1103/PhysRevLett.122.090501 |
| [53] | Devakul, T.; Williamson, D. J., Universal quantum computation using fractal symmetry-protected cluster phases, Phys. Rev. A, 98 (2018) · doi:10.1103/PhysRevA.98.022332 |
| [54] | Roberts, S.; Bartlett, S. D., Symmetry-protected self-correcting quantum memories, Phys. Rev. X, 10 (2020) · doi:10.1103/PhysRevX.10.031041 |
| [55] | Raussendorf, R.; Bravyi, S.; Harrington, J., Long-range quantum entanglement in noisy cluster states, Phys. Rev. A, 71 (2005) · doi:10.1103/PhysRevA.71.062313 |
| [56] | Raussendorf, R.; Harrington, J.; Goyal, K., A fault-tolerant one-way quantum computer, Ann. Phys., NY, 321, 2242-70 (2006) · Zbl 1101.81037 · doi:10.1016/j.aop.2006.01.012 |
| [57] | Raussendorf, R.; Harrington, J., Fault-tolerant quantum computation with high threshold in two dimensions, Phys. Rev. Lett., 98 (2007) · doi:10.1103/PhysRevLett.98.190504 |
| [58] | Raussendorf, R.; Harrington, J.; Goyal, K., Topological fault-tolerance in cluster state quantum computation, New J. Phys., 9, 199 (2007) · doi:10.1088/1367-2630/9/6/199 |
| [59] | Brown, B. J.; Roberts, S., Universal fault-tolerant measurement-based quantum computation, Phys. Rev. Res., 2 (2020) · doi:10.1103/PhysRevResearch.2.033305 |
| [60] | Jozsa, R.; Maarten, V. den N., Classical simulation complexity of extended Clifford circuits, Quantum Inf. Comput., 14, 633-48 (2014) · doi:10.26421/QIC14.7-8-7 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
