Connect with us

Quantum

Pauli error estimation via Population Recovery

Published

on


Steven T. Flammia1,2 and Ryan O’Donnell3

1AWS Center for Quantum Computing, USA
2IQIM, California Institute of Technology, USA
3Computer Science Department, Carnegie Mellon University, USA

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

Abstract

Motivated by estimation of quantum noise models, we study the problem of learning a Pauli channel, or more generally the Pauli error rates of an arbitrary channel. By employing a novel reduction to the “Population Recovery” problem, we give an extremely simple algorithm that learns the Pauli error rates of an $n$-qubit channel to precision $epsilon$ in $ell_infty$ using just $O(1/epsilon^2) log(n/epsilon)$ applications of the channel. This is optimal up to the logarithmic factors. Our algorithm uses only unentangled state preparation and measurements, and the post-measurement classical runtime is just an $O(1/epsilon)$ factor larger than the measurement data size. It is also impervious to a limited model of measurement noise where heralded measurement failures occur independently with probability $le 1/4$.
We then consider the case where the noise channel is close to the identity, meaning that the no-error outcome occurs with probability $1-eta$. In the regime of small $eta$ we extend our algorithm to achieve multiplicative precision $1 pm epsilon$ (i.e., additive precision $epsilon eta$) using just $Obigl(frac{1}{epsilon^2 eta}bigr) log(n/epsilon)$ applications of the channel.

The term “population recovery” is usually understood in the context of biology, where an endangered species (such as the gray wolf pictured here) is protected and their numbers begin to rebound. In the context of computer science, however, it refers to the ability to learn a probability distribution given only access to noisy samples. The “population” that we wish to learn (“recover”) is an unknown distribution on bit strings, and our ability to sample from this distribution is subject to independent noise, such as an erasure channel or a bit-flip channel.

In this work, we consider the problem of learning a probability distribution over Pauli operators; that is, we wish to learn a Pauli channel. Furthermore, we wish to do so using only very simple (product state) preparations and basis measurements. Learning Pauli channels with minimal resources is important for learning the errors in a noisy quantum computer and finding better ways to fix or otherwise mitigate those errors.

Our work shows that this problem reduces to the classical problem of population recovery with a certain type of asymmetric noise. We then show that the standard algorithms known in the literature for population recovery apply unchanged to this type of noise. This gives us very sample-efficient algorithms for learning Pauli channels that use very simple state preparations and measurements.

We also show a few other interesting tidbits. First, the algorithm is naturally robust to certain types of additional measurement noise. We can also extend the algorithm to handle the case where most of the time only a single Pauli occurs (say, the identity Pauli), and we wish to recover the remaining population with a precision that is relative to the frequency of the remainder population (a more stringent task). We show an interesting connection to Fourier analysis on boolean variables. Finally, we give an open source implementation in Julia of one of the algorithms.

► BibTeX data

► References

[1] F. Ban, X. Chen, A. Freilich, R. Servedio, and S. Sinha. Beyond trace reconstruction: Population recovery from the deletion channel. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science, pages 745–768, 2019, arXiv:1904.05532.
https:/​/​doi.org/​10.1109/​FOCS.2019.00050
arXiv:1904.05532

[2] F. Ban, X. Chen, R. A. Servedio, and S. Sinha. Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions. In D. Achlioptas and L. A. Végh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/​RANDOM 2019), volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pages 44:1–44:18, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, arXiv:1907.05964.
https:/​/​doi.org/​10.4230/​LIPIcs.APPROX-RANDOM.2019.44
arXiv:1907.05964

[3] L. Batman, R. Impagliazzo, C. Murray, and R. Paturi. Finding heavy hitters from lossy or noisy data. In Proceedings of the 16th Annual International Conference on Approximation Algorithms for Combinatorial Optimization Problems, pages 347–362, 2013.
https:/​/​doi.org/​10.1007/​978-3-642-40328-6_25

[4] C. H. Bennett and S. J. Wiesner. Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states. Phys. Rev. Lett., 69:2881–2884, Nov 1992.
https:/​/​doi.org/​10.1103/​PhysRevLett.69.2881

[5] C. L. Canonne. A short note on learning discrete distributions, 2020, arXiv:2002.11457.
arXiv:2002.11457

[6] C. Dankert. Efficient Simulation of Random Quantum States and Operators. PhD thesis, University of Waterloo, 2015, arXiv:quant-ph/​0512217.
arXiv:quant-ph/0512217

[7] A. De, R. O’Donnell, and R. Servedio. Sharp bounds for population recovery. Theory of Computing, 16(6):1–20, 2020, arXiv:1703.01474.
https:/​/​doi.org/​10.4086/​toc.2020.v016a006
arXiv:1703.01474

[8] A. De, M. Saks, and S. Tang. Noisy population recovery in polynomial time. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, pages 675–684, 2016, arXiv:1602.07616.
https:/​/​doi.org/​10.1109/​FOCS.2016.77
arXiv:1602.07616

[9] Z. Dvir, A. Rao, A. Wigderson, and A. Yehudayoff. Restriction access. In Proceedings of the 3nd Annual Innovations in Theoretical Computer Science, pages 19–33, 2012.
https:/​/​doi.org/​10.1145/​2090236.2090239

[10] S. Flammia and J. Wallman. Efficient estimation of Pauli channels. ACM Transactions on Quantum Computing, 1(1):1–32, 2020, arXiv:1907.12976.
https:/​/​doi.org/​10.1145/​3408039
arXiv:1907.12976

[11] S. T. Flammia. PauliPopRec, Github repository, 2021.
https:/​/​doi.org/​10.5281/​ZENODO.5327656

[12] A. Fujiwara and H. Imai. Quantum parameter estimation of a generalized Pauli channel. Journal of Physics A: Mathematical and General, 36(29):8093–8103, jul 2003.
https:/​/​doi.org/​10.1088/​0305-4470/​36/​29/​314

[13] O. Goldreich and L. Levin. A hard-core predicate for all one-way functions. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 25–32, 1989.
https:/​/​doi.org/​10.1145/​73007.73010

[14] R. Harper, S. T. Flammia, and J. J. Wallman. Efficient learning of quantum noise. Nature Physics, 16(12):1184–1188, Aug 2020, arXiv:1907.13022.
https:/​/​doi.org/​10.1038/​s41567-020-0992-8
arXiv:1907.13022

[15] R. Harper, W. Yu, and S. T. Flammia. Fast estimation of sparse quantum noise. PRX Quantum, 2(1):010322, Feb 2021, arXiv:2007.07901.
https:/​/​doi.org/​10.1103/​PRXQuantum.2.010322
arXiv:2007.07901

[16] M. Hayashi. Quantum Information Theory. Springer Berlin Heidelberg, 2nd edition, 2017.
https:/​/​doi.org/​10.1007/​978-3-662-49725-8

[17] J. Helsen, X. Xue, L. M. K. Vandersypen, and S. Wehner. A new class of efficient randomized benchmarking protocols. npj Quantum Information, 5(1):71, Aug. 2019, arXiv:1806.02048.
https:/​/​doi.org/​10.1038/​s41534-019-0182-7
arXiv:1806.02048

[18] E. Knill. Quantum computing with realistically noisy devices. Nature, 434(7029):39–44, mar 2005, arXiv:quant-ph/​0410199.
https:/​/​doi.org/​10.1038/​nature03350
arXiv:quant-ph/0410199

[19] S. Lovett and J. Zhang. Improved noisy population recovery, and reverse Bonami–Beckner inequality for sparse functions. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing, pages 137–142, 2015.
https:/​/​doi.org/​10.1145/​2746539.2746540

[20] S. Lovett and J. Zhang. Noisy population recovery from unknown noise. In Conference on Learning Theory, pages 1417–1431, 2017.

[21] A. Moitra and M. Saks. A polynomial time algorithm for lossy population recovery. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pages 110–116, 2013, arXiv:1302.1515.
https:/​/​doi.org/​10.1109/​FOCS.2013.20
arXiv:1302.1515

[22] A. Montanaro and T. J. Osborne. Quantum Boolean functions. Chicago Journal of Theoretical Computer Science, 2010(1):1–45, January 2010, arXiv:0810.2435.
https:/​/​doi.org/​10.4086/​cjtcs.2010.001
arXiv:0810.2435

[23] S. Narayanan. Improved algorithms for population recovery from the deletion channel. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1259–1278. Society for Industrial and Applied Mathematics, Jan. 2021, arXiv:2004.06828.
https:/​/​doi.org/​10.1137/​1.9781611976465.77
arXiv:2004.06828

[24] R. O’Donnell. Analysis of Boolean functions. Cambridge University Press, 2014, arXiv:2105.10386.
https:/​/​doi.org/​10.1017/​CBO9781139814782
arXiv:2105.10386

[25] Y. Polyanskiy, A. T. Suresh, and Y. Wu. Sample complexity of population recovery. In S. Kale and O. Shamir, editors, Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 1589–1618, Amsterdam, Netherlands, 07–10 Jul 2017. PMLR, arXiv:1702.05574.
arXiv:1702.05574

[26] B. Terhal. Quantum error correction for quantum memories. Reviews of Modern Physics, 87(2):307, 2015, arXiv:1302.3428.
https:/​/​doi.org/​10.1103/​RevModPhys.87.307
arXiv:1302.3428

[27] J. ur Rehman and H. Shin. Entanglement-free parameter estimation of generalized Pauli channels. Quantum, 5:490, Jul 2021, arXiv:2102.00740.
https:/​/​doi.org/​10.22331/​q-2021-07-01-490
arXiv:2102.00740

[28] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint. Cambridge University Press, 2019.
https:/​/​doi.org/​10.1017/​9781108627771

[29] J. Wallman and J. Emerson. Noise tailoring for scalable quantum computation via randomized compiling. Physical Review A, 94(5):052325, 2016, arXiv:1512.01098.
https:/​/​doi.org/​10.1103/​PhysRevA.94.052325
arXiv:1512.01098

[30] A. Wigderson and A. Yehudayoff. Population recovery and partial identification. Machine Learning, 102(1):29–56, 2016.
https:/​/​doi.org/​10.1007/​s10994-015-5489-9

Cited by

[1] Yunchao Liu, Matthew Otten, Roozbeh Bassirianjahromi, Liang Jiang, and Bill Fefferman, “Benchmarking near-term quantum computers via random circuit sampling”, arXiv:2105.05232.

[2] Thomas Wagner, Hermann Kampermann, Dagmar Bruß, and Martin Kliesch, “Pauli channels can be estimated from syndrome measurements in quantum error correction”, arXiv:2107.14252.

[3] Senrui Chen, Sisi Zhou, Alireza Seif, and Liang Jiang, “Quantum advantages for Pauli channel estimation”, arXiv:2108.08488.

[4] Steven T. Flammia, “Averaged circuit eigenvalue sampling”, arXiv:2108.05803.

The above citations are from SAO/NASA ADS (last updated successfully 2021-09-23 14:17:36). 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-23 14:17:34: Could not fetch cited-by data for 10.22331/q-2021-09-23-549 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-23-549/

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
Low_Car33ElfynEvansScott-Martin.jpg
Automotive4 days ago

Evans and TOYOTA GAZOO Racing Seal Second in Spain

Automotive4 days ago

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

Fintech4 days ago

PNC cuts nearly 600 apps for BBVA conversion

Automotive1 day ago

7 Secrets That Automakers Wish You Don’t Know

Blockchain10 hours ago

People’s payment attitude: Why cash Remains the most Common Means of Payment & How Technology and Crypto have more Advantages as a Means of payment

Blockchain1 day ago

What Is the Best Crypto IRA for Me? Use These 6 Pieces of Criteria to Find Out More

Aviation5 days ago

Vaccine passports for overseas travel to be rolled out this week

Cyber Security4 days ago

Spotify Web Player

Gaming1 day ago

New Steam Games You Might Have Missed In August 2021

IOT1 day ago

The Benefits of Using IoT SIM Card Technology

Blockchain1 day ago

The Most Profitable Cryptocurrencies on the Market

Esports4 days ago

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

Gaming1 day ago

How do casinos without an account work?

Esports5 days ago

New World Animal Instincts Quest Details

Startups10 hours ago

The 12 TikTok facts you should know

Esports4 days ago

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

Energy4 days ago

Segunda Conferência Ministerial de Energia da Rota e Cinturão é realizada em Qingdao

Blockchain1 day ago

What does swapping crypto mean?

Gaming1 day ago

Norway will crack down on the unlicensed iGaming market with a new gaming law

Payments4 days ago

Everyone is building a wallet

Trending