Connect with us

Quantum

Self-testing of a single quantum device under computational assumptions

Published

on


Tony Metger1 and Thomas Vidick2

1Institute for Theoretical Physics, ETH Zürich, 8093 Zürich, Switzerland
2Department of Computing and Mathematical Sciences, California Institute of Technology, CA 91125, United States

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Self-testing is a method to characterise an arbitrary quantum system based only on its classical input-output correlations, and plays an important role in device-independent quantum information processing as well as quantum complexity theory. Prior works on self-testing require the assumption that the system’s state is shared among multiple parties that only perform local measurements and cannot communicate. Here, we replace the setting of $textit{multiple non-communicating}$ parties, which is difficult to enforce in practice, by a $textit{single computationally bounded}$ party. Specifically, we construct a protocol that allows a classical verifier to robustly certify that a single computationally bounded quantum device must have prepared a Bell pair and performed single-qubit measurements on it, up to a change of basis applied to both the device’s state and measurements. This means that under computational assumptions, the verifier is able to certify the presence of entanglement, a property usually closely associated with two separated subsystems, inside a single quantum device. To achieve this, we build on techniques first introduced by Brakerski et al. (2018) and Mahadev (2018) which allow a classical verifier to constrain the actions of a quantum device assuming the device does not break post-quantum cryptography.

► BibTeX data

► References

[1] W. Aiello, S. Bhatt, R. Ostrovsky, and S. R. Rajagopalan. “Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP”, Automata, Languages and Programming – ICALP 2000, Lecture Notes in Computer Science, Springer, 463-474 (2000).
https:/​/​doi.org/​10.1007/​3-540-45022-X_39

[2] G. Alagic, A. M. Childs, A. B. Grilo, and S.-H. Hung. “Non-interactive classical verification of quantum computation”, Preprint (2019). arXiv:1911.08101.
arXiv:1911.08101

[3] M. Ben-Or, C. Crepeau, D. Gottesman, A. Hassidim, and A. Smith. “Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority”, IEEE 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 249-260 (2006).
https:/​/​doi.org/​10.1109/​FOCS.2006.68

[4] Z. Brakerski, P. Christiano, U. Mahadev, U. Vazirani, and T. Vidick. “A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device”, IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 320-331 (2018). arXiv:1804.00640v3.
https:/​/​doi.org/​10.1109/​FOCS.2018.00038
arXiv:1804.00640v3

[5] J. S. Bell. “On the Einstein Podolsky Rosen paradox”, Physics Physique Fizika 1, 195–200 (1964).
https:/​/​doi.org/​10.1103/​PhysicsPhysiqueFizika.1.195

[6] A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani. “On the complexity and verification of quantum random circuit sampling”, Nature Physics 15, 159–163 (2019).
https:/​/​doi.org/​10.1038/​s41567-018-0318-2

[7] A. Broadbent and A. B. Grilo. “QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge”, IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 196–205 (2020).
https:/​/​doi.org/​10.1109/​FOCS46700.2020.00027

[8] Z. Brakerski, V. Koppula, U. Vazirani, and T. Vidick. “Simpler Proofs of Quantumness”, Preprint (2020). arXiv:2005.04826.
arXiv:2005.04826

[9] K. Bharti, M. Ray, A. Varvitsiotis, N. A. Warsi, A. Cabello, and L.-C. Kwek. “Robust Self-Testing of Quantum Systems via Noncontextuality Inequalities”, Phys. Rev. Lett. 122, 250403 (2019). arXiv:1812.07265.
https:/​/​doi.org/​10.1103/​PhysRevLett.122.250403
arXiv:1812.07265

[10] A. Cojocaru, L. Colisson, E. Kashefi, and P. Wallden. “QFactory: Classically-Instructed Remote Secret Qubits Preparation”, Advances in Cryptology – ASIACRYPT 2019, Lecture Notes in Computer Science, Springer, 615-645 (2019). arXiv:1904.06303.
https:/​/​doi.org/​10.1007/​978-3-030-34578-5_22
arXiv:1904.06303

[11] N.-H. Chia, K.-M. Chung, and T. Yamakawa. “Classical Verification of Quantum Computations with Efficient Verifier”, Preprint (2019). arXiv:1912.00990.
arXiv:1912.00990

[12] A. Coladangelo, A. B. Grilo, S. Jeffery, and T. Vidick. “Verifier-on-a-leash: New schemes for verifiable delegated quantum computation, with quasilinear resources”, Advances in Cryptology – EUROCRYPT 2019, Lecture Notes in Computer Science, Springer 11478 LNCS, 247-277 (2019). arXiv:1708.07359.
https:/​/​doi.org/​10.1007/​978-3-030-17659-4_9
arXiv:1708.07359

[13] C. Crépeau, D. Gottesman, and A. Smith. “Secure Multi-Party Quantum Computation”, Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 643-652 (2002).
https:/​/​doi.org/​10.1145/​509907.510000

[14] A. Coladangelo, K. T. Goh, and V. Scarani. “All pure bipartite entangled states can be self-tested”, Nature Communications 8, 15485 (2017). arXiv:1611.08062.
https:/​/​doi.org/​10.1038/​ncomms15485
arXiv:1611.08062

[15] R. Colbeck. Quantum and relativistic protocols for secure multi-party computation, PhD Thesis, University of Cambridge (2006). arXiv:0911.3814.
arXiv:0911.3814

[16] A. Coladangelo, T. Vidick, and T. Zhang. “Non-interactive zero-knowledge arguments for QMA, with preprocessing”, Annual International Cryptology Conference (CRYPTO), 799–828 (2020).
https:/​/​doi.org/​10.1007/​978-3-030-56877-1_28

[17] Y. Dodis, S. Halevi, R. D. Rothblum, and D. Wichs. “Spooky Encryption and Its Applications”, Advances in Cryptology – CRYPTO 2016, Lecture Notes in Computer Science, Springer, 93-122 (2016).
https:/​/​doi.org/​10.1007/​978-3-662-53015-3_4

[18] W. T. Gowers and O. Hatami. “Inverse and stability theorems for approximate representations of finite groups”, Sbornik: Mathematics 208, 1784 (2017).
https:/​/​doi.org/​10.1070/​SM8872

[19] A. Gheorghiu and T. Vidick. “Computationally-secure and composable remote state preparation”, IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 1024–1033 (2019).
https:/​/​doi.org/​10.1109/​FOCS.2019.00066

[20] Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen. “${MIP}^*={RE}$”, Preprint (2020). arXiv:2001.04383.
arXiv:2001.04383

[21] Y. T. Kalai, R. Raz, and R. D. Rothblum. “How to Delegate Computations: The Power of No-Signaling Proofs”, Proceedings of the 46th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 485-494 (2014).
https:/​/​doi.org/​10.1145/​2591796.2591809

[22] U. Mahadev. “Classical Verification of Quantum Computations”, IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 259-267 (2018). arXiv:1804.01082v2.
https:/​/​doi.org/​10.1109/​FOCS.2018.00033
arXiv:1804.01082v2

[23] T. Metger, Y. Dulek, A. Coladangelo, and R. Arnon-Friedman. “Device-independent quantum key distribution from computational assumptions”, Preprint (2020). arXiv:2010.04175.
arXiv:2010.04175

[24] C. A. Miller and Y. Shi. “Universal Security for Randomness Expansion from the Spot-Checking Protocol”, SIAM Journal on Computing 46, 1304-1335 (2017). arXiv:1411.6608.
https:/​/​doi.org/​10.1137/​15M1044333
arXiv:1411.6608

[25] D. Mayers and A. Yao. “Self Testing Quantum Apparatus”, Quantum Info. Comput. 4, 273-286 (2004). arXiv:quant-ph/​0307205.
arXiv:quant-ph/0307205
https:/​/​dl.acm.org/​doi/​10.5555/​2011827.2011830

[26] M. McKague, T. H. Yang, and V. Scarani. “Robust self-testing of the singlet”, Journal of Physics A: Mathematical and Theoretical 45, 455304 (2012).
https:/​/​doi.org/​10.1088/​1751-8113/​45/​45/​455304

[27] A. Natarajan and J. Wright. “NEEXP in MIP*”, IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 510-518 (2019). arXiv:1904.05870.
https:/​/​doi.org/​10.1109/​FOCS.2019.00039
arXiv:1904.05870

[28] S. Popescu and D. Rohrlich. “Which states violate Bell’s inequality maximally?”, Physics Letters A 169, 411–414 (1992).
https:/​/​doi.org/​10.1016/​0375-9601(92)90819-8

[29] R. Raz. “A parallel repetition theorem”, SIAM Journal on Computing 27, 763–803 (1998).
https:/​/​doi.org/​10.1137/​S0097539795280895

[30] O. Regev. “On Lattices, Learning with Errors, Random Linear Codes, and Cryptography”, J. ACM 56 (2009).
https:/​/​doi.org/​10.1145/​1568318.1568324

[31] B. W. Reichardt, F. Unger, and U. Vazirani. “Classical command of quantum systems”, Nature 496, 456 (2013). arXiv:1209.0449.
https:/​/​doi.org/​10.1038/​nature12035
arXiv:1209.0449

[32] I. Šupić and J. Bowles. “Self-testing of quantum systems: a review”, Preprint (2019). arXiv:1904.10042.
https:/​/​doi.org/​10.22331/​q-2020-09-30-337
arXiv:1904.10042

[33] V. Scarani. Bell Nonlocality, Oxford University Press (2019).

[34] S. J. Summers and R. Werner. “Maximal violation of Bell’s inequalities is generic in quantum field theory”, Communications in Mathematical Physics 110, 247–259 (1987).
https:/​/​doi.org/​10.1007/​BF01207366

[35] T. Vidick. The complexity of entangled games. PhD thesis, 2011.
https:/​/​digitalassets.lib.berkeley.edu/​etd/​ucb/​text/​Vidick_berkeley_0028E_11907.pdf

[36] U. Vazirani and T. Vidick. “Certifiable Quantum Dice: Or, True Random Number Generation Secure against Quantum Adversaries”, Proceedings of the 44th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 61-76 (2012). arXiv:1111.6054.
https:/​/​doi.org/​10.1145/​2213977.2213984
arXiv:1111.6054

[37] T. Vidick and T. Zhang. “Classical proofs of quantum knowledge”, Preprint (2020). arXiv:2005.01691.
arXiv:2005.01691

[38] M. Wilde. “From Classical to Quantum Shannon Theory”, Preprint (2011). arXiv:1106.1445v8.
https:/​/​doi.org/​10.1017/​9781316809976.001
arXiv:1106.1445v8

Cited by

[1] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik, “Noisy intermediate-scale quantum (NISQ) algorithms”, arXiv:2101.08448.

[2] Alexandru Gheorghiu and Matty J. Hoban, “Estimating the entropy of shallow circuit outputs is hard”, arXiv:2002.12814.

[3] Thomas Vidick and Tina Zhang, “Classical proofs of quantum knowledge”, arXiv:2005.01691.

[4] Yu Cai, Baichu Yu, Pooja Jayachandran, Nicolas Brunner, Valerio Scarani, and Jean-Daniel Bancal, “Entanglement for any definition of two subsystems”, Physical Review A 103 5, 052432 (2021).

[5] Tony Metger, Yfke Dulek, Andrea Coladangelo, and Rotem Arnon-Friedman, “Device-independent quantum key distribution from computational assumptions”, arXiv:2010.04175.

[6] Tomoyuki Morimae, “Information-theoretically-sound non-interactive classical verification of quantum computing with trusted center”, arXiv:2003.10712.

[7] Tomoyuki Morimae and Yuki Takeuchi, “Trusted center verification model and classical channel remote state preparation”, arXiv:2008.05033.

[8] Kishor Bharti, Maharshi Ray, Zhen-Peng Xu, Masahito Hayashi, Leong-Chuan Kwek, and Adán Cabello, “Graph-Theoretic Framework for Self-Testing in Bell Scenarios”, arXiv:2104.13035.

The above citations are from SAO/NASA ADS (last updated successfully 2021-09-16 17:11:41). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2021-09-16 17:11:40: Could not fetch cited-by data for 10.22331/q-2021-09-16-544 from Crossref. This is normal if the DOI was registered recently.

PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.

Source: https://quantum-journal.org/papers/q-2021-09-16-544/

Quantum

Trapping Sets of Quantum LDPC Codes

Published

on


Nithin Raveendran and Bane Vasić

Department of Electrical and Computer Engineering, University of Arizona, Tucson, AZ 85721, USA

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Iterative decoders for finite length quantum low-density parity-check (QLDPC) codes are attractive because their hardware complexity scales only linearly with the number of physical qubits. However, they are impacted by short cycles, detrimental graphical configurations known as trapping sets (TSs) present in a code graph as well as symmetric degeneracy of errors. These factors significantly degrade the decoder decoding probability performance and cause so-called error floor. In this paper, we establish a systematic methodology by which one can identify and classify quantum trapping sets (QTSs) according to their topological structure and decoder used. The conventional definition of a TS from classical error correction is generalized to address the syndrome decoding scenario for QLDPC codes. We show that the knowledge of QTSs can be used to design better QLDPC codes and decoders. Frame error rate improvements of two orders of magnitude in the error floor regime are demonstrated for some practical finite-length QLDPC codes without requiring any post-processing.

Quantum low-density parity-check (QLDPC) codes have recently gained popularity as an important class of quantum error correction codes due to their ability to realize scalable fault-tolerant quantum computers with constant overhead and are decodable using efficient iterative decoders. However, QLDPC code’s decoding performance is impacted by short cycles and detrimental graphical configurations present in their code graph. Such a performance degradation at low noise values – referred to as error floor effect will be severe especially in the case of practically useful finite length QLDPC codes. In classical LDPC coding literature, these harmful configurations classified as $textit{trapping sets}$ (TSs) have been well studied and have aided to develop low-complexity iterative decoders that surpass the conventional belief propagation decoder. However, TSs have never been formally studied in the context of QLDPC codes and their decoding. In this work, we introduce the concept of $textit{Quantum Trapping Sets}$ (QTSs) by investigating the failure configurations for syndrome-based iterative decoders. We establish a systematic methodology by which one can identify and classify QTSs according to their topological structure and decoder used. The conventional definition of a TS from classical error correction is generalized to address the syndrome decoding scenario for QLDPC codes. As a summary, we observe two types of QTSs – one is similar to classical TSs and the other is referred to as symmetric stabilizer TSs – these are unique to QLDPC codes. The properties of symmetric stabilizer TSs are distinct and specific to the QLDPC decoding problem and hence, will be instrumental in exploiting the degeneracy of QLDPC codes to the decoder’s advantage. Furthermore, we demonstrate the two advantages of studying QTSs – (1) Design better QLDPC codes – ability to construct QLDPC codes devoid of harmful QTSs, (2) Design better decoders without post-processing steps – ability to devise new decoding algorithms that escape from harmful QTSs and have low error floors.

► BibTeX data

► References

[1] N. Raveendran and B. Vasić. Trapping set analysis of finite-length quantum LDPC codes. In IEEE Int. Symp. on Inform. Theory, pages 1564–1569, 2021. 10.1109/​ISIT45174.2021.9518154.
https:/​/​doi.org/​10.1109/​ISIT45174.2021.9518154

[2] D. J. C. MacKay, G. Mitchison, and P. L. McFadden. Sparse-graph codes for quantum error correction. IEEE Trans. on Inform. Theory, 50 (10): 2315–2330, Oct. 2004. 10.1109/​TIT.2004.834737.
https:/​/​doi.org/​10.1109/​TIT.2004.834737

[3] P. W. Shor. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A, 52: R2493–R2496, Oct. 1995. 10.1103/​PhysRevA.52.R2493.
https:/​/​doi.org/​10.1103/​PhysRevA.52.R2493

[4] D. Gottesman. Fault-tolerant quantum computation with constant overhead. Quantum Inform. and Computation, 14 (15–16): 1338–1372, Nov. 2014. 10.26421/​QIC14.15-16-5.
https:/​/​doi.org/​10.26421/​QIC14.15-16-5

[5] A. A. Kovalev and L. P. Pryadko. Fault tolerance of quantum low-density parity check codes with sublinear distance scaling. Phys. Rev. A, 87: 020304, Feb. 2013a. 10.1103/​PhysRevA.87.020304.
https:/​/​doi.org/​10.1103/​PhysRevA.87.020304

[6] Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo. The road from classical to quantum codes: A hashing bound approaching design procedure. IEEE Access, 3: 146–176, 2015a. 10.1109/​ACCESS.2015.2405533.
https:/​/​doi.org/​10.1109/​ACCESS.2015.2405533

[7] Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo. Fifteen years of quantum LDPC coding and improved decoding strategies. IEEE Access, 3: 2492–2519, 2015b. 10.1109/​ACCESS.2015.2503267.
https:/​/​doi.org/​10.1109/​ACCESS.2015.2503267

[8] J.-P. Tillich and G. Zémor. Quantum LDPC codes with positive rate and minimum distance proportional to $n^{1/​2}$. Proc. IEEE Int. Symp. on Inform. Theory, pages 799–803, Jul. 2009. 10.1109/​ISIT.2009.5205648.
https:/​/​doi.org/​10.1109/​ISIT.2009.5205648

[9] A. Leverrier, J.-P. Tillich, and G. Zémor. Quantum expander codes. In Proc. IEEE 56th Ann. Symp. on Foundations of Computer Science, pages 810–824, Berkeley, CA, USA, Oct. 2015. 10.1109/​FOCS.2015.55.
https:/​/​doi.org/​10.1109/​FOCS.2015.55

[10] P. Panteleev and G. Kalachev. Quantum LDPC codes with almost linear minimum distance. arXiv preprint:2012.04068, 2020. URL https:/​/​arxiv.org/​abs/​2012.04068.
arXiv:2012.04068

[11] K.-Y. Kuo and C.-Y. Lai. Refined belief propagation decoding of sparse-graph quantum codes. IEEE Journal on Selected Areas in Information Theory, 1 (2): 487–498, 2020. 10.1109/​jsait.2020.3011758.
https:/​/​doi.org/​10.1109/​jsait.2020.3011758

[12] C.-Y. Lai and K.-Y. Kuo. Log-domain decoding of quantum LDPC codes over binary finite fields. IEEE Trans. on Quantum Engineering, 2021. 10.1109/​TQE.2021.3113936.
https:/​/​doi.org/​10.1109/​TQE.2021.3113936

[13] D. Poulin and Y. Chung. On the iterative decoding of sparse quantum codes. Quantum Inform. and Computation, 8 (10): 987–1000, Nov. 2008. 10.26421/​QIC8.10-8.
https:/​/​doi.org/​10.26421/​QIC8.10-8

[14] T. J. Richardson. Error floors of LDPC codes. In Proc. 41st Ann. Allerton Conf. Commun., Contr. and Comp., pages 1426–1435, Monticello, IL, USA, Sept. 2003. URL https:/​/​web.stanford.edu/​class/​ee388/​papers/​ErrorFloors.pdf.
https:/​/​web.stanford.edu/​class/​ee388/​papers/​ErrorFloors.pdf

[15] P. Panteleev and G. Kalachev. Degenerate quantum LDPC codes with good finite length performance. arXiv preprint:1904.02703, 2019. URL https:/​/​arxiv.org/​abs/​1904.02703.
arXiv:1904.02703

[16] B. Vasić, D. V. Nguyen, and S. K. Chilappagari. Chapter 6 – failures and error floors of iterative decoders. In Channel Coding: Theory, Algorithms, and Applications: Academic Press Library in Mobile and Wireless Commun., pages 299–341, Oxford, 2014. Academic Press. 10.1016/​B978-0-12-396499-1.00006-6.
https:/​/​doi.org/​10.1016/​B978-0-12-396499-1.00006-6

[17] J. Roffe, D. R. White, S. Burton, and E. Campbell. Decoding across the quantum low-density parity-check code landscape. Phys. Rev. Research, 2: 043423, Dec. 2020. 10.1103/​PhysRevResearch.2.043423.
https:/​/​doi.org/​10.1103/​PhysRevResearch.2.043423

[18] M. P. C. Fossorier and S. Lin. Soft-decision decoding of linear block codes based on ordered statistics. IEEE Trans. on Inform. Theory, 41: 1379 – 1396, 10 1995. 10.1109/​18.412683.
https:/​/​doi.org/​10.1109/​18.412683

[19] M. Baldi, N. Maturo, E. Paolini, and F. Chiaraluce. On the use of ordered statistics decoders for low-density parity-check codes in space telecommand links. EURASIP J. Wirel. Commun. Netw., 2016 (272): 1– 15, 2016. 10.1186/​s13638-016-0769-z.
https:/​/​doi.org/​10.1186/​s13638-016-0769-z

[20] A. Rigby, J. C. Olivier, and P. Jarvis. Modified belief propagation decoders for quantum low-density parity-check codes. Phys. Rev. A, 100: 012330, Jul. 2019. 10.1103/​physreva.100.012330.
https:/​/​doi.org/​10.1103/​physreva.100.012330

[21] J. X. Li and P. O. Vontobel. Pseudocodeword-based decoding of quantum stabilizer codes. In Proc. IEEE Int. Symp. on Inform. Theory, pages 2888–2892, 2019. 10.1109/​ISIT.2019.8849833.
https:/​/​doi.org/​10.1109/​ISIT.2019.8849833

[22] N. Raveendran, D. Declercq, and B. Vasić. A sub-graph expansion-contraction method for error floor computation. IEEE Trans. on Commun., 68 (7): 3984–3995, 2020. 10.1109/​TCOMM.2020.2988676.
https:/​/​doi.org/​10.1109/​TCOMM.2020.2988676

[23] S. K. Planjery, D. Declercq, L. Danjean, and B. Vasić. Finite alphabet iterative decoders, Part I: Decoding beyond belief propagation on the binary symmetric channel. IEEE Trans. on Commun., 61 (10): 4033–4045, Nov. 2013. 10.1109/​TCOMM.2013.090513.120443.
https:/​/​doi.org/​10.1109/​TCOMM.2013.090513.120443

[24] A. R. Calderbank and P. W. Shor. Good quantum error-correcting codes exist. Physical Review A, 54 (2): 1098–1105, Aug. 1996. ISSN 1094-1622. 10.1103/​physreva.54.1098.
https:/​/​doi.org/​10.1103/​physreva.54.1098

[25] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, New York, NY, USA, 10th edition, 2011. 10.1017/​CBO9780511976667.
https:/​/​doi.org/​10.1017/​CBO9780511976667

[26] D. Gottesman. Stabilizer codes and quantum error correction. Ph.D. Dissertation, California Institute of Technology, 1997. 10.7907/​rzr7-dt72. URL https:/​/​arxiv.org/​abs/​quant-ph/​9705052.
https:/​/​doi.org/​10.7907/​rzr7-dt72
arXiv:quant-ph/9705052

[27] M. M. Wilde. Logical operators of quantum codes. Phys. Rev. A, 79: 062322, Jun. 2009. 10.1103/​PhysRevA.79.062322.
https:/​/​doi.org/​10.1103/​PhysRevA.79.062322

[28] N. Raveendran, P. J. Nadkarni, S. S. Garani, and B. Vasić. Stochastic resonance decoding for quantum LDPC codes. In Proc. IEEE Int. Conf. on Commun., pages 1–6, May 2017. 10.1109/​ICC.2017.7996747.
https:/​/​doi.org/​10.1109/​ICC.2017.7996747

[29] M. Karimi and A. H. Banihashemi. Efficient algorithm for finding dominant trapping sets of LDPC codes. IEEE Trans. on Inform. Theory, 58 (11): 6942–6958, Nov. 2012. 10.1109/​TIT.2012.2205663.
https:/​/​doi.org/​10.1109/​TIT.2012.2205663

[30] D. V. Nguyen, S. K. Chilappagari, M. W. Marcellin, and B. Vasić. On the construction of structured LDPC codes free of small trapping sets. IEEE Trans. on Inform. Theory, 58 (4): 2280–2302, Apr. 2012. 10.1109/​TIT.2011.2173733.
https:/​/​doi.org/​10.1109/​TIT.2011.2173733

[31] S. M. Khatami, L. Danjean, D. V. Nguyen, and B. Vasić. An efficient exhaustive low-weight codeword search for structured LDPC codes. In Proc. Inform. Theory and Applications Workshop, pages 1 – 10, San Diego, CA, USA, Feb. 10–15 2013. 10.1109/​ITA.2013.6502981.
https:/​/​doi.org/​10.1109/​ITA.2013.6502981

[32] Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo. Construction of quantum LDPC codes from classical row-circulant QC-LDPCs. IEEE Commun. Letters, 20 (1): 9–12, Jan. 2016. 10.1109/​LCOMM.2015.2494020.
https:/​/​doi.org/​10.1109/​LCOMM.2015.2494020

[33] M. Hagiwara and H. Imai. Quantum quasi-cyclic LDPC codes. In Proc. IEEE Int. Symp. on Inform. Theory, pages 806–810, Jun. 2007. 10.1109/​ISIT.2007.4557323.
https:/​/​doi.org/​10.1109/​ISIT.2007.4557323

[34] Y. Xie and J. Yuan. Reliable quantum LDPC codes over GF(4). In Proc. IEEE Globecom Workshops, pages 1–5, Dec. 2016. 10.1109/​GLOCOMW.2016.7849021.
https:/​/​doi.org/​10.1109/​GLOCOMW.2016.7849021

[35] A. A. Kovalev and L. P. Pryadko. Quantum kronecker sum-product low-density parity-check codes with finite rate. Phys. Rev. A, 88: 012311, Jul. 2013b. 10.1103/​PhysRevA.88.012311.
https:/​/​doi.org/​10.1103/​PhysRevA.88.012311

[36] A. A. Kovalev and L. P. Pryadko. Improved quantum hypergraph-product LDPC codes. In Proc. IEEE Int. Symp. on Inform. Theory, pages 348–352, Jul. 2012. 10.1109/​ISIT.2012.6284206.
https:/​/​doi.org/​10.1109/​ISIT.2012.6284206

[37] M. P. C. Fossorier. Quasi-cyclic low-density parity-check codes from circulant permutation matrices. IEEE Trans. on Inform. Theory, 50 (8): 1788–1793, Aug. 2004. 10.1109/​TIT.2004.831841.
https:/​/​doi.org/​10.1109/​TIT.2004.831841

[38] D. E. Hocevar. A reduced complexity decoder architecture via layered decoding of LDPC codes. In Proc. IEEE Workshop on Signal Processing Systems, pages 107–112, 2004. 10.1109/​SIPS.2004.1363033.
https:/​/​doi.org/​10.1109/​SIPS.2004.1363033

[39] E. Sharon, S. Litsyn, and J. Goldberger. Efficient serial message-passing schedules for LDPC decoding. IEEE Trans. on Inform. Theory, 53 (11): 4076–4091, 2007. 10.1109/​TIT.2007.907507.
https:/​/​doi.org/​10.1109/​TIT.2007.907507

[40] N. Raveendran and B. Vasić. Trapping set analysis of horizontal layered decoder. In Proc. IEEE Int. Conf. on Commun., pages 1–6, May 2018. 10.1109/​ICC.2018.8422965.
https:/​/​doi.org/​10.1109/​ICC.2018.8422965

[41] Y.-J. Wang, B. C. Sanders, B.-M. Bai, and X.-M. Wang. Enhanced feedback iterative decoding of sparse quantum codes. IEEE Trans. on Inform. Theory, 58 (2): 1231–1241, Feb. 2012. 10.1109/​TIT.2011.2169534.
https:/​/​doi.org/​10.1109/​TIT.2011.2169534

Cited by

[1] Kao-Yueh Kuo and Ching-Yi Lai, “Exploiting Degeneracy in Belief Propagation Decoding of Quantum Codes”, arXiv:2104.13659.

[2] Kao-Yueh Kuo, I-Chun Chern, and Ching-Yi Lai, “Decoding of Quantum Data-Syndrome Codes via Belief Propagation”, arXiv:2102.01984.

[3] Ching-Yi Lai and Kao-Yueh Kuo, “Log-domain decoding of quantum LDPC codes over binary finite fields”, arXiv:2104.00304.

[4] Patricio Fuentes, Josu Etxezarreta Martinez, Pedro M. Crespo, and Javier Garcia-Frias, “On the logical error rate of sparse quantum codes”, arXiv:2108.10645.

The above citations are from SAO/NASA ADS (last updated successfully 2021-10-14 18:26:04). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2021-10-14 18:26:02: Could not fetch cited-by data for 10.22331/q-2021-10-14-562 from Crossref. This is normal if the DOI was registered recently.

PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.

Source: https://quantum-journal.org/papers/q-2021-10-14-562/

Continue Reading

Quantum

Entangled symmetric states and copositive matrices

Published

on


Carlo Marconi1, Albert Aloy2, Jordi Tura3,4, and Anna Sanpera1,5

1Física Teòrica: Informació i Fenòmens Quàntics. Departament de Física, Universitat Autònoma de Barcelona, 08193 Bellaterra, Spain
2ICFO – Institut de Ciències Fotòniques, The Barcelona Institute of Science and Technology, 08860 Castelldefels (Barcelona), Spain
3Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Str. 1, 85748 Garching, Germany
4Instituut-Lorentz, Universiteit Leiden, P.O. Box 9506, 2300 RA Leiden, The Netherlands
5ICREA, Pg. Lluís Companys 23, 08010 Barcelona, Spain

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Entanglement in symmetric quantum states and the theory of copositive matrices are intimately related concepts. For the simplest symmetric states, i.e., the diagonal symmetric (DS) states, it has been shown that there exists a correspondence between exceptional (non-exceptional) copositive matrices and non-decomposable (decomposable) Entanglement Witnesses (EWs). Here we show that EWs of symmetric, but not DS, states can also be constructed from extended copositive matrices, providing new examples of bound entangled symmetric states, together with their corresponding EWs, in arbitrary odd dimensions.

Entanglement is one of the most intriguing phenomena in quantum physics whose implications have profound consequences not only from a theoretical point of view but also in light of some computational tasks that would be otherwise unfeasible with classical systems.
For this reason, deciding whether a quantum state is entangled or not, is a problem of paramount importance whose solution, unfortunately, is known to be NP-hard in the general scenario.
In some cases, however, symmetries provide a useful framework to recast the separability problem in a simpler way, thus reducing the original complexity of this task.
In this work we focus on symmetric states, i.e., states that are invariant under permutations of the parties, showing how, in the case of the qudits, the characterization of the entanglement can be accomplished by means of a class of matrices known as copositive. In particular, we establish a connection between entanglement witnesses, i.e., hermitian operators that are able to detect entanglement, and copositive matrices, showing how only a subset of them, dubbed as exceptional, can be used to assess PPT-entanglement in any dimension, with the PPT-entangled edge states detected by the so-called extremal matrices.
Finally we illustrate our findings discussing some examples of families of PPT-entangled states in 3-level and 4-level systems, along with the entanglement witnesses that detect them.
We conjecture that any PPT-entangled state of two qudits can be detected by means of an entanglement witness of the form that we propose.

► BibTeX data

► References

[1] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki. Quantum entanglement. Reviews of modern physics, 81 (2): 865, 2009. 10.1103/​RevModPhys.81.865.
https:/​/​doi.org/​10.1103/​RevModPhys.81.865

[2] Charles H Bennett, Herbert J Bernstein, Sandu Popescu, and Benjamin Schumacher. Concentrating partial entanglement by local operations. Physical Review A, 53 (4): 2046, 1996. 10.1103/​PhysRevA.53.2046.
https:/​/​doi.org/​10.1103/​PhysRevA.53.2046

[3] Leonid Gurvits. Classical deterministic complexity of edmonds’ problem and quantum entanglement. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 10–19, 2003. 10.1145/​780542.780545.
https:/​/​doi.org/​10.1145/​780542.780545

[4] Asher Peres. Separability criterion for density matrices. Physical Review Letters, 77 (8): 1413, 1996. 10.1103/​PhysRevLett.77.1413.
https:/​/​doi.org/​10.1103/​PhysRevLett.77.1413

[5] Barbara M Terhal and Karl Gerd H Vollbrecht. Entanglement of formation for isotropic states. Physical Review Letters, 85 (12): 2625, 2000. 10.1103/​PhysRevLett.85.2625.
https:/​/​doi.org/​10.1103/​PhysRevLett.85.2625

[6] Maciej Lewenstein, Barabara Kraus, J Ignacio Cirac, and P Horodecki. Optimization of entanglement witnesses. Physical Review A, 62 (5): 052310, 2000. 10.1103/​PhysRevA.62.052310.
https:/​/​doi.org/​10.1103/​PhysRevA.62.052310

[7] Dariusz Chruściński and Gniewomir Sarbicki. Entanglement witnesses: construction, analysis and classification. Journal of Physics A: Mathematical and Theoretical, 47 (48): 483001, 2014. 10.1088/​1751-8113/​47/​48/​483001.
https:/​/​doi.org/​10.1088/​1751-8113/​47/​48/​483001

[8] Maciej Lewenstein, B Kraus, P Horodecki, and JI Cirac. Characterization of separable states and entanglement witnesses. Physical Review A, 63 (4): 044304, 2001. 10.1103/​PhysRevA.63.044304.
https:/​/​doi.org/​10.1103/​PhysRevA.63.044304

[9] Fernando GSL Brandao. Quantifying entanglement with witness operators. Physical Review A, 72 (2): 022310, 2005. 10.1103/​physreva.72.022310.
https:/​/​doi.org/​10.1103/​physreva.72.022310

[10] Karl Gerd H Vollbrecht and Reinhard F Werner. Entanglement measures under symmetry. Physical Review A, 64 (6): 062307, 2001. 10.1103/​PhysRevA.64.062307.
https:/​/​doi.org/​10.1103/​PhysRevA.64.062307

[11] Géza Tóth and Otfried Gühne. Separability criteria and entanglement witnesses for symmetric quantum states. Applied Physics B, 98 (4): 617–622, 2010. 10.1007/​s00340-009-3839-7.
https:/​/​doi.org/​10.1007/​s00340-009-3839-7

[12] Tilo Eggeling and Reinhard F Werner. Separability properties of tripartite states with u $otimes$ u $otimes$ u $otimes$ symmetry. Physical Review A, 63 (4): 042111, 2001. 10.1103/​physreva.63.042111.
https:/​/​doi.org/​10.1103/​physreva.63.042111

[13] Jordi Tura, Albert Aloy, Ruben Quesada, Maciej Lewenstein, and Anna Sanpera. Separability of diagonal symmetric states: a quadratic conic optimization problem. Quantum, 2: 45, 2018. 10.22331/​q-2018-01-12-45.
https:/​/​doi.org/​10.22331/​q-2018-01-12-45

[14] Anna Sanpera, Dagmar Bruß, and Maciej Lewenstein. Schmidt-number witnesses and bound entanglement. Physical Review A, 63 (5): 050301, 2001. 10.1103/​PhysRevA.63.050301.
https:/​/​doi.org/​10.1103/​PhysRevA.63.050301

[15] Lieven Clarisse. Construction of bound entangled edge states with special ranks. Physics Letters A, 359 (6): 603–607, 2006. 10.1016/​j.physleta.2006.07.045.
https:/​/​doi.org/​10.1016/​j.physleta.2006.07.045

[16] Seung-Hyeok Kye and Hiroyuki Osaka. Classification of bi-qutrit positive partial transpose entangled edge states by their ranks. Journal of mathematical physics, 53 (5): 052201, 2012. 10.1063/​1.4712302.
https:/​/​doi.org/​10.1063/​1.4712302

[17] Lin Chen and Dragomir Ž Ðoković. Description of rank four entangled states of two qutrits having positive partial transpose. Journal of mathematical physics, 52 (12): 122203, 2011. 10.1063/​1.3663837.
https:/​/​doi.org/​10.1063/​1.3663837

[18] Jon Magne Leinaas, Jan Myrheim, and Per Øyvind Sollid. Low-rank extremal positive-partial-transpose states and unextendible product bases. Phys. Rev. A, 81: 062330, Jun 2010. 10.1103/​PhysRevA.81.062330.
https:/​/​doi.org/​10.1103/​PhysRevA.81.062330

[19] Nengkun Yu. Separability of a mixture of dicke states. Physical Review A, 94 (6): 060101, 2016. 10.1103/​PhysRevA.94.060101.
https:/​/​doi.org/​10.1103/​PhysRevA.94.060101

[20] Katta G. Murty and Santosh N. Kabadi. Some np-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39: 117–129, 1987. 10.1007/​BF02592948.
https:/​/​doi.org/​10.1007/​BF02592948

[21] Li Ping and Feng Yu Yu. Criteria for copositive matrices of order four. Linear algebra and its applications, 194: 109–124, 1993. 10.1016/​0024-3795(93)90116-6.
https:/​/​doi.org/​10.1016/​0024-3795(93)90116-6

[22] J-B Hiriart-Urruty and Alberto Seeger. A variational approach to copositive matrices. SIAM review, 52 (4): 593–629, 2010. 10.1137/​090750391.
https:/​/​doi.org/​10.1137/​090750391

[23] Palahenedi Hewage Diananda. On non-negative forms in real variables some or all of which are non-negative. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 58, pages 17–25. Cambridge University Press, 1962. 10.1017/​s0305004100036185.
https:/​/​doi.org/​10.1017/​s0305004100036185

[24] Marshall Hall and Morris Newman. Copositive and completely positive quadratic forms. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 59, pages 329–339. Cambridge University Press, 1963. 10.1017/​s0305004100036951.
https:/​/​doi.org/​10.1017/​s0305004100036951

[25] Charles Johnson and Robert Reams. Constructing copositive matrices from interior matrices. The Electronic Journal of Linear Algebra, 17: 9–20, 2008. 10.13001/​1081-3810.1245.
https:/​/​doi.org/​10.13001/​1081-3810.1245

[26] Alan J Hoffman and Francisco Pereira. On copositive matrices with- 1, 0, 1 entries. Journal of Combinatorial Theory, Series A, 14 (3): 302–309, 1973. 10.1016/​0097-3165(73)90006-x.
https:/​/​doi.org/​10.1016/​0097-3165(73)90006-x

[27] Dariusz Chruściński and Andrzej Kossakowski. Circulant states with positive partial transpose. Phys. Rev. A, 76: 032308, Sep 2007. 10.1103/​PhysRevA.76.032308.
https:/​/​doi.org/​10.1103/​PhysRevA.76.032308

[28] Andrew C Doherty, Pablo A Parrilo, and Federico M Spedalieri. Complete family of separability criteria. Physical Review A, 69 (2): 022308, 2004. 10.1103/​PhysRevA.69.022308.
https:/​/​doi.org/​10.1103/​PhysRevA.69.022308

[29] Andrew C Doherty, Pablo A Parrilo, and Federico M Spedalieri. Distinguishing separable and entangled states. Physical Review Letters, 88 (18): 187904, 2002. 10.1103/​physrevlett.88.187904.
https:/​/​doi.org/​10.1103/​physrevlett.88.187904

Cited by

[1] Adam Burchardt, Jakub Czartowski, and Karol Życzkowski, “Entanglement in highly symmetric multipartite quantum states”, Physical Review A 104 2, 022426 (2021).

[2] Hari krishnan S V, Ashish Ranjan, and Manik Banik, “State space structure of tripartite quantum systems”, Physical Review A 104 2, 022437 (2021).

[3] Joonwoo Bae, Anindita Bera, Dariusz Chruściński, Beatrix C. Hiesmayr, and Daniel McNulty, “How many measurements are needed to detect bound entangled states?”, arXiv:2108.01109.

[4] Beatrix C. Hiesmayr, “Free versus Bound Entanglement: Machine learning tackling a NP-hard problem”, arXiv:2106.03977.

The above citations are from SAO/NASA ADS (last updated successfully 2021-10-07 15:38:09). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2021-10-07 15:38:08: Could not fetch cited-by data for 10.22331/q-2021-10-07-561 from Crossref. This is normal if the DOI was registered recently.

PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.

Source: https://quantum-journal.org/papers/q-2021-10-07-561/

Continue Reading

Quantum

The Quantum Supremacy Tsirelson Inequality

Published

on

William Kretschmer

Department of Computer Science, The University of Texas at Austin, Austin, TX 78712, USA

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

A leading proposal for verifying near-term quantum supremacy experiments on noisy random quantum circuits is linear cross-entropy benchmarking. For a quantum circuit $C$ on $n$ qubits and a sample $z in {0,1}^n$, the benchmark involves computing $|langle z|C|0^n rangle|^2$, i.e. the probability of measuring $z$ from the output distribution of $C$ on the all zeros input. Under a strong conjecture about the classical hardness of estimating output probabilities of quantum circuits, no polynomial-time classical algorithm given $C$ can output a string $z$ such that $|langle z|C|0^nrangle|^2$ is substantially larger than $frac{1}{2^n}$ (Aaronson and Gunn, 2019). On the other hand, for a random quantum circuit $C$, sampling $z$ from the output distribution of $C$ achieves $|langle z|C|0^nrangle|^2 approx frac{2}{2^n}$ on average (Arute et al., 2019).
In analogy with the Tsirelson inequality from quantum nonlocal correlations, we ask: can a polynomial-time quantum algorithm do substantially better than $frac{2}{2^n}$? We study this question in the query (or black box) model, where the quantum algorithm is given oracle access to $C$. We show that, for any $varepsilon ge frac{1}{mathrm{poly}(n)}$, outputting a sample $z$ such that $|langle z|C|0^nrangle|^2 ge frac{2 + varepsilon}{2^n}$ on average requires at least $Omegaleft(frac{2^{n/4}}{mathrm{poly}(n)}right)$ queries to $C$, but not more than $Oleft(2^{n/3}right)$ queries to $C$, if $C$ is either a Haar-random $n$-qubit unitary, or a canonical state preparation oracle for a Haar-random $n$-qubit state. We also show that when $C$ samples from the Fourier distribution of a random Boolean function, the naive algorithm that samples from $C$ is the optimal 1-query algorithm for maximizing $|langle z|C|0^nrangle|^2$ on average.

Recent quantum supremacy experiments were verified using a statistical test called the “Linear Cross-Entropy Benchmark” (or Linear XEB). This benchmark was chosen because of complexity-theoretic evidence that an efficient quantum algorithm can achieve a higher Linear XEB score than any possible efficient classical algorithm.

We argue that this upper bound on the power of classical algorithms for the Linear XEB is analogous to the Bell inequality in nonlocal correlations: both capture inherent limits on the power of classical information and computation that may be violated in the quantum setting. Motivated by this connection, we ask: what is the quantum supremacy analogue of the Tsirelson inequality? That is, what is the highest Linear XEB score achievable by an efficient quantum algorithm? We give evidence that the naive quantum algorithm for passing the benchmark is essentially optimal in this regard.

► BibTeX data

► References

[1] Scott Aaronson. Random circuit sampling: Thoughts and open problems. The Quantum Wave in Computing, 2020. URL https:/​/​simons.berkeley.edu/​talks/​tbd-124.
https:/​/​simons.berkeley.edu/​talks/​tbd-124

[2] Scott Aaronson and Lijie Chen. Complexity-Theoretic Foundations of Quantum Supremacy Experiments. In Ryan O’Donnell, editor, 32nd Computational Complexity Conference (CCC 2017), volume 79 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1–22:67, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-040-8. 10.4230/​LIPIcs.CCC.2017.22. URL http:/​/​drops.dagstuhl.de/​opus/​volltexte/​2017/​7527.
https:/​/​doi.org/​10.4230/​LIPIcs.CCC.2017.22
http:/​/​drops.dagstuhl.de/​opus/​volltexte/​2017/​7527

[3] Scott Aaronson and Sam Gunn. On the classical hardness of spoofing linear cross-entropy benchmarking. Theory of Computing, 16 (11): 1–8, 2020. 10.4086/​toc.2020.v016a011. URL http:/​/​www.theoryofcomputing.org/​articles/​v016a011.
https:/​/​doi.org/​10.4086/​toc.2020.v016a011
http:/​/​www.theoryofcomputing.org/​articles/​v016a011

[4] Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler. Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. In Shubhangi Saraf, editor, 35th Computational Complexity Conference (CCC 2020), volume 169 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1–7:47, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. ISBN 978-3-95977-156-6. 10.4230/​LIPIcs.CCC.2020.7. URL https:/​/​drops.dagstuhl.de/​opus/​volltexte/​2020/​12559.
https:/​/​doi.org/​10.4230/​LIPIcs.CCC.2020.7
https:/​/​drops.dagstuhl.de/​opus/​volltexte/​2020/​12559

[5] Dorit Aharonov, Alexei Kitaev, and Noam Nisan. Quantum circuits with mixed states. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98, page 20–30, New York, NY, USA, 1998. Association for Computing Machinery. ISBN 0897919629. 10.1145/​276698.276708. URL https:/​/​doi.org/​10.1145/​276698.276708.
https:/​/​doi.org/​10.1145/​276698.276708

[6] Andris Ambainis. Understanding quantum algorithms via query complexity. In Proceedings of the 2018 International Congress of Mathematicians, volume 3, pages 3249–3270, 2018. 10.1142/​9789813272880_0181.
https:/​/​doi.org/​10.1142/​9789813272880_0181

[7] Andris Ambainis, Loïck Magnin, Martin Roetteler, and Jeremie Roland. Symmetry-assisted adversaries for quantum state generation. In Proceedings of the 2011 IEEE 26th Annual Conference on Computational Complexity, CCC ’11, page 167–177, USA, 2011. IEEE Computer Society. ISBN 9780769544113. 10.1109/​CCC.2011.24. URL https:/​/​doi.org/​10.1109/​CCC.2011.24.
https:/​/​doi.org/​10.1109/​CCC.2011.24

[8] Andris Ambainis, Ansis Rosmanis, and Dominique Unruh. Quantum attacks on classical proof systems: The hardness of quantum rewinding. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS ’14, page 474–483, USA, 2014. IEEE Computer Society. ISBN 9781479965175. 10.1109/​FOCS.2014.57. URL https:/​/​doi.org/​10.1109/​FOCS.2014.57.
https:/​/​doi.org/​10.1109/​FOCS.2014.57

[9] Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf. Quantum Coupon Collector. In Steven T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. ISBN 978-3-95977-146-7. 10.4230/​LIPIcs.TQC.2020.10. URL https:/​/​drops.dagstuhl.de/​opus/​volltexte/​2020/​12069.
https:/​/​doi.org/​10.4230/​LIPIcs.TQC.2020.10
https:/​/​drops.dagstuhl.de/​opus/​volltexte/​2020/​12069

[10] Frank Arute, Kunal Arya, Ryan Babbush, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779): 505–510, 2019. 10.1038/​s41586-019-1666-5. URL https:/​/​doi.org/​10.1038/​s41586-019-1666-5.
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[11] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. J. ACM, 48 (4): 778–797, July 2001. ISSN 0004-5411. 10.1145/​502090.502097. URL https:/​/​doi.org/​10.1145/​502090.502097.
https:/​/​doi.org/​10.1145/​502090.502097

[12] John Bell. On the Einstein-Podolsky-Rosen paradox. Physics, 1: 195–200, Nov 1964. 10.1103/​PhysicsPhysiqueFizika.1.195. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysicsPhysiqueFizika.1.195.
https:/​/​doi.org/​10.1103/​PhysicsPhysiqueFizika.1.195

[13] Aleksandrs Belovs. Variations on quantum adversary, 2015.
arXiv:1504.06943

[14] Aleksandrs Belovs and Ansis Rosmanis. Tight quantum lower bound for approximate counting with quantum states, 2020.
arXiv:2002.06879

[15] Fernando G. S. L. Brandão, Aram W. Harrow, and Michał Horodecki. Local random quantum circuits are approximate polynomial-designs. Communications in Mathematical Physics, 346 (2): 397–434, 2016. 10.1007/​s00220-016-2706-8. URL https:/​/​doi.org/​10.1007/​s00220-016-2706-8.
https:/​/​doi.org/​10.1007/​s00220-016-2706-8

[16] Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum cryptanalysis of hash and claw-free functions. SIGACT News, 28 (2): 14–19, June 1997. ISSN 0163-5700. 10.1145/​261342.261346. URL https:/​/​doi.org/​10.1145/​261342.261346.
https:/​/​doi.org/​10.1145/​261342.261346

[17] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information, volume 305 of Contemporary Mathematics, pages 53–74. American Mathematical Society, 2002. ISBN 9780821821404. 10.1090/​conm/​305.
https:/​/​doi.org/​10.1090/​conm/​305

[18] Mark Bun and Justin Thaler. Dual lower bounds for approximate degree and Markov-Bernstein inequalities. Inf. Comput., 243 (C): 2–25, August 2015. ISSN 0890-5401. 10.1016/​j.ic.2014.12.003. URL https:/​/​doi.org/​10.1016/​j.ic.2014.12.003.
https:/​/​doi.org/​10.1016/​j.ic.2014.12.003

[19] Boris Cirel’son (Tsirelson). Quantum generalizations of Bell’s inequality. Letters in Mathematical Physics, 4 (2): 93–100, 1980. 10.1007/​BF00417500. URL https:/​/​doi.org/​10.1007/​BF00417500.
https:/​/​doi.org/​10.1007/​BF00417500

[20] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett., 23: 880–884, Oct 1969. 10.1103/​PhysRevLett.23.880. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.23.880.
https:/​/​doi.org/​10.1103/​PhysRevLett.23.880

[21] Richard Cleve, Peter Høyer, Benjamin Toner, and John Watrous. Consequences and limits of nonlocal strategies. In Proceedings of the 19th IEEE Annual Conference on Computational Complexity, CCC ’04, page 236–249, USA, 2004. IEEE Computer Society. ISBN 0769521207. 10.1109/​CCC.2004.1313847.
https:/​/​doi.org/​10.1109/​CCC.2004.1313847

[22] Aram Harrow and Saeed Mehraban. Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates, 2018.
arXiv:1809.06957

[23] Norman L. Johnson and Samuel Kotz. Urn models and their application: an approach to modern discrete probability theory. Wiley, 1977. ISBN 9780471446309.

[24] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols, and Theodore J. Yoder. Hamiltonian simulation with optimal sample complexity. npj Quantum Information, 3 (1): 13, 2017. 10.1038/​s41534-017-0013-7. URL https:/​/​doi.org/​10.1038/​s41534-017-0013-7.
https:/​/​doi.org/​10.1038/​s41534-017-0013-7

[25] William Kretschmer. The Quantum Supremacy Tsirelson Inequality. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1–13:13, Dagstuhl, Germany, 2021. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. ISBN 978-3-95977-177-1. 10.4230/​LIPIcs.ITCS.2021.13. URL https:/​/​drops.dagstuhl.de/​opus/​volltexte/​2021/​13552.
https:/​/​doi.org/​10.4230/​LIPIcs.ITCS.2021.13
https:/​/​drops.dagstuhl.de/​opus/​volltexte/​2021/​13552

[26] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy. Quantum query complexity of state conversion. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS ’11, page 344–353, USA, 2011. IEEE Computer Society. ISBN 9780769545714. 10.1109/​FOCS.2011.75. URL https:/​/​doi.org/​10.1109/​FOCS.2011.75.
https:/​/​doi.org/​10.1109/​FOCS.2011.75

[27] Nathan Lindzey and Ansis Rosmanis. A Tight Lower Bound For Non-Coherent Index Erasure. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 59:1–59:37, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-134-4. 10.4230/​LIPIcs.ITCS.2020.59. URL https:/​/​drops.dagstuhl.de/​opus/​volltexte/​2020/​11744.
https:/​/​doi.org/​10.4230/​LIPIcs.ITCS.2020.59
https:/​/​drops.dagstuhl.de/​opus/​volltexte/​2020/​11744

[28] Frederic Magniez, Ashwin Nayak, Jeremie Roland, and Miklos Santha. Search via quantum walk. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07, page 575–584, New York, NY, USA, 2007. Association for Computing Machinery. ISBN 9781595936318. 10.1145/​1250790.1250874. URL https:/​/​doi.org/​10.1145/​1250790.1250874.
https:/​/​doi.org/​10.1145/​1250790.1250874

[29] Ryan O’Donnell. Analysis of Boolean Functions. Cambridge University Press, USA, 2014. ISBN 1107038324. 10.1017/​CBO9781139814782.
https:/​/​doi.org/​10.1017/​CBO9781139814782

[30] Martin Raab and Angelika Steger. “Balls into bins” – a simple and tight analysis. In Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM ’98, pages 159–170, Berlin, Heidelberg, 1998. Springer-Verlag. ISBN 354065142X. 10.1007/​3-540-49543-6_13.
https:/​/​doi.org/​10.1007/​3-540-49543-6_13

[31] Ben W. Reichardt. Reflections for quantum query algorithms. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’11, page 560–569, USA, 2011. Society for Industrial and Applied Mathematics. 10.1137/​1.9781611973082.44.
https:/​/​doi.org/​10.1137/​1.9781611973082.44

[32] Alfréd Rényi. On the theory of order statistics. Acta Mathematica Academiae Scientiarum Hungarica, 4 (3): 191–231, 1953. 10.1007/​BF02127580. URL https:/​/​doi.org/​10.1007/​BF02127580.
https:/​/​doi.org/​10.1007/​BF02127580

Cited by

[1] Daniel Stilck França and Raul Garcia-Patron, “A game of quantum advantage: linking verification and simulation”, arXiv:2011.12173.

[2] Nicholas LaRacuente, “Quantum Oracle Separations from Complex but Easily Specified States”, arXiv:2104.07247.

[3] Scott Aaronson, “Open Problems Related to Quantum Query Complexity”, arXiv:2109.06917.

The above citations are from SAO/NASA ADS (last updated successfully 2021-10-07 11:15:15). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2021-10-07 11:15:13: Could not fetch cited-by data for 10.22331/q-2021-10-07-560 from Crossref. This is normal if the DOI was registered recently.

PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.

Source: https://quantum-journal.org/papers/q-2021-10-07-560/

Continue Reading

Quantum

Mathematicians Prove Melting Ice Stays Smooth

Published

on

Drop an ice cube into a glass of water. You can probably picture the way it starts to melt. You also know that no matter what shape it takes, you’ll never see it melt into something like a snowflake, composed everywhere of sharp edges and fine cusps.

Mathematicians model this melting process with equations. The equations work well, but it’s taken 130 years to prove that they conform to obvious facts about reality. Now, in a paper posted in March, Alessio Figalli and Joaquim Serra of the Swiss Federal Institute of Technology Zurich and Xavier Ros-Oton of the University of Barcelona have established that the equations really do match intuition. Snowflakes in the model may not be impossible, but they are extremely rare and entirely fleeting.

“These results open a new perspective on the field,” said Maria Colombo of the Swiss Federal Institute of Technology Lausanne. “There was no such deep and precise understanding of this phenomenon previously.”

The question of how ice melts in water is called the Stefan problem, named after the physicist Josef Stefan, who posed it in 1889. It is the most important example of a “free boundary” problem, where mathematicians consider how a process like the diffusion of heat makes a boundary move. In this case, the boundary is between ice and water.

For many years, mathematicians have tried to understand the complicated models of these evolving boundaries. To make progress, the new work draws inspiration from previous studies on a different type of physical system: soap films. It builds on them to prove that along the evolving boundary between ice and water, sharp spots like cusps or edges rarely form, and even when they do, they immediately disappear.

These sharp spots are called singularities, and, it turns out, they are as ephemeral in the free boundaries of mathematics as they are in the physical world.

Melting Hourglasses

Consider, again, an ice cube in a glass of water. The two substances are made of the same water molecules, but the water is in two different phases: solid and liquid. A boundary exists where the two phases meet. But as heat from the water transfers into the ice, the ice melts and the boundary moves. Eventually, the ice — and the boundary along with it — disappear.

Intuition might tell us that this melting boundary always remains smooth. After all, you do not cut yourself on sharp edges when you pull a piece of ice from a glass of water. But with a little imagination, it is easy to conceive of scenarios where sharp spots emerge.

Take a piece of ice in the shape of an hourglass and submerge it. As the ice melts, the waist of the hourglass becomes thinner and thinner until the liquid eats all the way through. At the moment this happens, what was once a smooth waist becomes two pointy cusps, or singularities.

“This is one of those problems that naturally exhibits singularities,” said Giuseppe Mingione of the University of Parma. “It’s the physical reality that tells you that.

Yet reality also tells us that the singularities are controlled. We know that cusps should not last long, because the warm water should rapidly melt them down. Perhaps if you started with a huge ice block built entirely out of hourglasses, a snowflake might form. But it still wouldn’t last more than an instant.

In 1889 Stefan subjected the problem to mathematical scrutiny, spelling out two equations that describe melting ice. One describes the diffusion of heat from the warm water into the cool ice, which shrinks the ice while causing the region of water to expand. A second equation tracks the changing interface between ice and water as the melting process proceeds. (In fact, the equations can also describe the situation where the ice is so cold that it causes the surrounding water to freeze — but in the present work, the researchers ignore that possibility.)

“The important thing is to understand where the two phases decide to switch from one to the other,” said Colombo.

It took almost 100 years until, in the 1970s, mathematicians proved that these equations have a solid foundation. Given some starting conditions — a description of the initial temperature of the water and the initial shape of the ice — it’s possible to run the model indefinitely to describe exactly how the temperature (or a closely related quantity called the cumulative temperature) changes with time.

But they found nothing to preclude the model from arriving at scenarios that are improbably weird. The equations might describe an ice-water boundary that forms into a forest of cusps, for example, or a sharp snowflake that stays perfectly still. In other words, they couldn’t rule out the possibility that the model might output nonsense. The Stefan problem became a problem of showing that the singularities in these situations are actually well controlled.

Otherwise, it would mean that the ice melting model was a spectacular failure — one that had fooled generations of mathematicians into believing it was more solid than it is.

Soapy Inspiration

In the decade before mathematicians began to understand the ice melting equations, they made tremendous progress on the mathematics of soap films.

If you dip two wire rings in a soapy solution and then separate them, a soap film forms between them. Surface tension will pull the film as taut as possible, forming it into a shape called a catenoid — a kind of caved-in cylinder. This shape forms because it bridges the two rings with the least amount of surface area, making it an example of what mathematicians call a minimal surface.

Soap films are modeled by their own unique set of equations. By the 1960s, mathematicians had made progress in understanding them, but they didn’t know how weird their solutions could be. Just as in the Stefan problem, the solutions might be unacceptably strange, describing soap films with countless singularities that are nothing like the smooth films we expect.

In 1961 and 1962, Ennio De Giorgi, Wendell Fleming and others invented an elegant process for determining whether the situation with singularities was as bad as feared.

Suppose you have a solution to the soap film equations that describes the shape of the film between two boundary surfaces, like the set of two rings. Focus in on an arbitrary point on the film’s surface. What does the geometry near this point look like? Before we know anything about it, it could have any kind of feature imaginable — anything from a sharp cusp to a smooth hill. Mathematicians devised a method for zooming in on the point, as though they had a microscope with infinite power. They proved that as you zoom in, all you see is a flat plane.

“Always. That’s it,” said Ros-Oton.

This flatness implied that the geometry near that point could not be singular. If the point were located on a cusp, mathematicians would see something more like a wedge, not a plane. And since they chose the point randomly, they could conclude that all points on the film must look like a smooth plane when you peer at them up close. Their work established that the entire film must be smooth — unplagued by singularities.

Mathematicians wanted to use the same methods to deal with the Stefan problem, but they soon realized that with ice, things were not as simple. Unlike soap films, which always look smooth, melting ice really does exhibit singularities. And while a soap film stays put, the line between ice and water is always in motion. This posed an additional challenge that another mathematician would tackle later.

From Films to Ice

In 1977, Luis Caffarelli reinvented a mathematical magnifying glass for the Stefan problem. Rather than zooming in on a soap film, he figured out how to zoom in on the boundary between ice and water.

“This was his great intuition,” said Mingione. “He was able to transport these methods from the minimal surface theory of de Giorgi to this more general setting.”

When mathematicians zoomed in on solutions to the soap film equations, they saw only flatness. But when Caffarelli zoomed in on the frozen boundary between ice and water, he sometimes saw something totally different: frozen spots surrounded almost entirely by warmer water. These points corresponded to icy cusps — singularities — which become stranded by the retreat of the melting boundary.

Caffarelli proved singularities exist in the mathematics of melting ice. He also devised a way of estimating how many there are. At the exact spot of an icy singularity, the temperature is always zero degrees Celsius, because the singularity is made out of ice. That is a simple fact. But remarkably, Caffarelli found that as you move away from the singularity, the temperature increases in a clear pattern: If you move one unit in distance away from a singularity and into the water, the temperature rises by approximately one unit of temperature. If you move two units away, the temperature rises by approximately four.

This is called a parabolic relationship, because if you graph temperature as a function of distance, you get approximately the shape of a parabola. But because space is three-dimensional, you can graph the temperature in three different directions leading away from the singularity, not just one. The temperature therefore looks like a three-dimensional parabola, a shape called a paraboloid.

Altogether, Caffarelli’s insight provided a clear way of sizing up singularities along the ice-water boundary. Singularities are defined as points where the temperature is zero degrees Celsius and paraboloids describe the temperature at and around the singularity. Therefore, anywhere the paraboloid equals zero you have a singularity.

So how many places are there where a paraboloid can equal zero? Imagine a paraboloid composed of a sequence of parabolas stacked side by side. Paraboloids like these can take a minimum value — a value of zero — along an entire line. This means that each of the singularities Caffarelli observed could actually be the size of a line, an infinitely thin icy edge, rather than just a single icy point. And since many lines can be put together to form a surface, his work left open the possibility that a set of singularities could fill the entire boundary surface. If this was true, it would mean that the singularities in the Stefan problem were completely out of control.

“It would be a disaster for the model. Complete chaos,” said Figalli, who won the Fields Medal, math’s highest honor, in 2018.

However, Caffarelli’s result was only a worst-case scenario. It established the maximum size of the potential singularities, but it said nothing about how often singularities actually occur in the equations, or how long they last. By 2019, Figalli, Ros-Oton and Serra had figured out a remarkable way to find out more.

Imperfect Patterns

To solve the Stefan problem, Figalli, Ros-Oton and Serra needed to prove that singularities that crop up in the equations are controlled: There aren’t a lot of them and they don’t last long. To do that, they needed a comprehensive understanding of all the different types of singularities that could possibly form.

Caffarelli had made progress on understanding how singularities develop as ice melts, but there was a feature of the process he didn’t know how to address. He recognized that the water temperature around a singularity follows a paraboloid ­­pattern. He also recognized that it doesn’t quite follow this pattern exactly — there’s a small deviation between a perfect paraboloid and the actual way the water temperature looks.

Figalli, Ros-Oton and Serra shifted the microscope onto this deviation from the paraboloid pattern. When they zoomed in on this small imperfection — a whisper of coolness waving off of the boundary — they discovered that it had its own kinds of patterns which gave rise to different types of singularities.

“They go beyond the parabolic scaling,” said Sandro Salsa of the Polytechnic University of Milan. “Which is amazing.”

They were able to show that all of these new types of singularities disappeared rapidly — just as they do in nature —  except for two that were particularly enigmatic. Their last challenge was to prove that these two types also vanish as soon as they appear, foreclosing the possibility that anything like a snowflake might endure.

Vanishing Cusps

The first type of singularity had come up before, in 2000. A mathematician named Frederick Almgren had investigated it in an intimidating 1,000-page paper about soap films, which was only published by his wife, Jean Taylor — another expert on soap films — after he died.

While mathematicians had shown that soap films are always smooth in three dimensions, Almgren proved that in four dimensions, a new kind of “branching” singularity can appear, making the soap films sharp in strange ways. These singularities are profoundly abstract and impossible to visualize neatly. Yet Figalli, Ros-Oton and Serra realized that very similar singularities form along the melting boundary between ice and water.

“The connection is a bit mysterious,” Serra said. “Sometimes in mathematics, things develop in unexpected ways.”

They used Almgren’s work to show that the ice around one of these branching singularities must have a conical pattern that looks the same as you keep zooming in. And unlike the paraboloid pattern for the temperature, which implies that a singularity might exist along a whole line, a conical pattern can only have a sharp singularity at a single point. Using this fact, they showed that these singularities are isolated in space and time. As soon as they form, they are gone.

The second kind of singularity was even more mysterious. To get a sense of it, imagine submerging a thin sheet of ice into water. It will shrink and shrink and suddenly disappear all at once. But just before that moment, it will form a sheetlike singularity, a two-dimensional wall as sharp as a razor.

At certain points, the researchers managed to zoom in to find an analogous scenario: two fronts of ice collapsing toward the point as if it were situated inside a thin sheet of ice. These points were not exactly singularities, but locations where a singularity was about to form. The question was whether the two fronts near these points collapsed at the same time. If that happened, a sheetlike singularity would form for only one perfect moment before it vanished. In the end, they proved this is in fact how the scenario plays out in the equations.

“This somehow confirms the intuition,” said Daniela De Silva of Barnard College.

Having shown that the exotic branching and sheetlike singularities were both rare, the researchers could make the general statement that all singularities for the Stefan problem are rare.

“If you choose randomly a time, then the probability of seeing a singular point is zero,” Ros-Oton said.

The mathematicians say that the technical details of the work will take time to digest. But they are confident that the results will lay the groundwork for advances on numerous other problems. The Stefan problem is a foundational example for an entire subfield of math where boundaries move. But as for the Stefan problem itself, and the mathematics of how ice cubes melt in water?

“This is closed,” Salsa said.

PlatoAi. Web3 Reimagined. Data Intelligence Amplified.

Click here to access.

Source: https://www.quantamagazine.org/mathematicians-prove-melting-ice-stays-smooth-20211006/

Continue Reading
Esports5 days ago

The best teams in Hearthstone Mercenaries

Fintech3 days ago

PNC cuts nearly 600 apps for BBVA conversion

Aviation4 days ago

Vaccine passports for overseas travel to be rolled out this week

Esports2 days ago

New World team share details of upcoming server transfers in Q&A

Esports5 days ago

How Many Chapters are in the Demon Slayer Game?

Cyber Security3 days ago

Spotify Web Player

AI4 days ago

When to Contact an Attorney After a Car Accident

Payments3 days ago

Everyone is building a wallet

Esports3 days ago

How TFT Set 6 Hextech Augments work: full list and updates

Automotive3 days ago

This Toyota Mirai 1:10 Scale RC Car Actually Runs On Hydrogen

AI4 days ago

5 Ways to Attract Clients with Law Firm SEO

Esports5 days ago

Demon Slayer: Kimetsu no Yaiba – The Hinokami Chronicles Character Tier List

Esports4 days ago

The 10 Legends of Runeterra characters most likely to turn into League champions

Low_Car33ElfynEvansScott-Martin.jpg
Automotive3 days ago

Evans and TOYOTA GAZOO Racing Seal Second in Spain

Blockchain5 hours ago

The Most Profitable Cryptocurrencies on the Market

Cleantech4 days ago

US & Denmark Unveil Big Plans For Wind Power

Esports3 days ago

How to play Scream Deathmatch Game Mode in Call of Duty: Black Ops Cold War

Supply Chain4 days ago

Top 10 hydraulic cylinder manufacturers in China

Energy2 days ago

People’s Daily Online: uma pesquisa do Instituto de Zoologia de Kumming mostrou um aumento estável da população de pavões verdes, uma espécie ameaçada de extinção

Esports5 days ago

Only 6,900 pick’ems remain perfect after group B’s second round-robin at the 2021 World Championship

Trending