Connect with us


Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm




Jessica Lemieux1, Bettina Heim2, David Poulin1,3, Krysta Svore2, and Matthias Troyer2

1Département de Physique & Institut Quantique, Université de Sherbrooke, Québec, Canada
2Quantum Architecture and Computation Group, Microsoft Research, Redmond, WA 98052, USA
3Canadian Institute for Advanced Research, Toronto, Ontario, Canada M5G 1Z8

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


We present a detailed circuit implementation of Szegedy’s quantization of the Metropolis-Hastings walk. This quantum walk is usually defined with respect to an oracle. We find that a direct implementation of this oracle requires costly arithmetic operations. We thus reformulate the quantum walk, circumventing its implementation altogether by closely following the classical Metropolis-Hastings walk. We also present heuristic quantum algorithms that use the quantum walk in the context of discrete optimization problems and numerically study their performances. Our numerical results indicate polynomial quantum speedups in heuristic settings.

► BibTeX data

► References

[1] Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the thirty-fifth ACM symposium on Theory of computing – STOC ’03, page 20, New York, New York, USA, 2003. ACM Press. ISBN 1581136749. 10.1145/​780542.780546.

[2] Andris Ambainis. Quantum walk algorithm for element distinctness. In Proceedings – Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 22–31, 2004. 10.1109/​focs.2004.54.

[3] Francisco Barahona. On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical and General, 15: 3241–3253, 1982. 10.1088/​0305-4470/​15/​10/​028.

[4] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. Divincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Physical Review A, 52 (5): 3457–3467, nov 1995. ISSN 10502947. 10.1103/​PhysRevA.52.3457.

[5] Alex Bocharov, Martin Roetteler, and Krysta M. Svore. Efficient synthesis of probabilistic quantum circuits with fallback. Physical Review A – Atomic, Molecular, and Optical Physics, 91 (5): 052317, may 2015. ISSN 10941622. 10.1103/​PhysRevA.91.052317.

[6] S. Boixo, E. Knill, and R. D. Somma. Fast quantum algorithms for traversing paths of eigenstates. may 2010. URL https:/​/​​abs/​1005.3034.

[7] Sergio Boixo, Emanuel Knill, and Rolando Somma. Eigenpath traversal by phase randomization. Quantum Information and Computation, 9 (9&10): 0833, 2009. URL http:/​/​​abs/​0903.1652.

[8] N Cody Jones, James D Whitfield, Peter L McMahon, Man-Hong Yung, Rodney Van Meter, Alán Aspuru-Guzik, and Yoshihisa Yamamoto. Faster quantum chemistry simulation on fault-tolerant quantum computers. New Journal of Physics, 14 (11): 115023, nov 2012. ISSN 1367-2630. 10.1088/​1367-2630/​14/​11/​115023.

[9] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum Computation by Adiabatic Evolution. jan 2000. URL http:/​/​​abs/​quant-ph/​0001106.

[10] Roy J. Glauber. Time-dependent statistics of the Ising model. Journal of Mathematical Physics, 4 (2): 294–307, feb 1963. ISSN 00222488. 10.1063/​1.1703954.

[11] Jeongwan Haah. Product Decomposition of Periodic Functions in Quantum Signal Processing. jun 2018. 10.22331/​q-2019-10-07-190.

[12] W K Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57 (1): 97–109, apr 1970. ISSN 0006-3444. 10.1093/​biomet/​57.1.97.

[13] Janus Collaboration, F. Belletti, M. Cotallo, A. Cruz, L. A. Fernández, A. Gordillo, M. Guidetti, A. Maiorano, F. Mantovani, E. Marinari, V. Martín-Mayor, A. Muñoz-Sudupe, D. Navarro, G. Parisi, S. Pérez-Gaviro, M. Rossi, J. J. Ruiz-Lorenzo, S. F. Schifano, D. Sciretti, A. Tarancón, R. Tripiccione, and J. L. Velasco. JANUS: an FPGA-based System for High Performance Scientific Computing. Computing in Science & Engineering, 11 (1): 48–58, 2009. 10.1109/​MCSE.2009.11.

[14] Janus Collaboration, M. Baity-Jesi, R. A. Banos, A. Cruz, L. A. Fernandez, J. M. Gil-Narvion, A. Gordillo-Guerrero, M. Guidetti, D. Iniguez, A. Maiorano, F. Mantovani, E. Marinari, V. Martin-Mayor, J. Monforte-Garcia, A. Munoz Sudupe, D. Navarro, G. Parisi, M. Pivanti, S. Perez-Gaviro, F. Ricci-Tersenghi, J. J. Ruiz-Lorenzo, S. F. Schifano, B. Seoane, A. Tarancon, P. Tellez, R. Tripiccione, and D. Yllanes. Reconfigurable computing for Monte Carlo simulations: results and prospects of the Janus project. The European Physical Journal Special Topics, 210 (33), 2012. 10.1140/​epjst/​e2012-01636-9.

[15] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220 (4598): 671–680, 1983. ISSN 00368075. 10.1126/​science.220.4598.671.

[16] A. Yu. Kitaev. Quantum measurements and the Abelian Stabilizer Problem. nov 1995. URL http:/​/​​abs/​quant-ph/​9511026.

[17] Jessica Lemieux, Guillaume Duclos-Cianci, David Sénéchal, and David Poulin. Resource estimate for quantum many-body ground state preparation on a quantum computer. 2020. URL https:/​/​​abs/​2006.04650.

[18] Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization. oct 2016. 10.22331/​q-2019-07-12-163.

[19] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian Simulation by Quantum Signal Processing. Physical Review Letters, 118 (1): 010501, jan 2017. ISSN 10797114. 10.1103/​PhysRevLett.118.010501.

[20] Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang. Methodology of resonant equiangular composite quantum gates. Physical Review X, 6 (4): 041067, dec 2016. ISSN 21603308. 10.1103/​PhysRevX.6.041067.

[21] F. Magniez, A. Nayak, J. Roland, and M. Santha. Search via quantum walk. SIAM Journal on Computing, 40: 142–164. 10.1137/​090745854.

[22] Chris Marriott and John Watrous. Quantum Arthur-Merlin games. In Computational Complexity, volume 14, pages 122–152. Springer, jun 2005. 10.1007/​s00037-005-0194-x.

[23] Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21 (6): 1087–1092, jun 1953. ISSN 00219606. 10.1063/​1.1699114.

[24] Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, David Wecker, John M. Martinis, Daniel A. Lidar, and Matthias Troyer. Defining and detecting quantum speedup. Science, 345 (6195): 420–424, jul 2014. ISSN 10959203. 10.1126/​science.1252319.

[25] Neil J Ross and Peter Selinger. Optimal ancilla-free Clifford+T approximation of Z-rotations. Quantum Information and Computation, 16 (11&12): 0901, 2016. URL http:/​/​​abs/​1403.2975.

[26] Terry Rudolph and Lov Grover. A 2 rebit gate universal for quantum computing. oct 2002. URL https:/​/​​abs/​quant-ph/​0210187.

[27] R. D. Somma, S. Boixo, H. Barnum, and E. Knill. Quantum simulations of classical annealing processes. Physical Review Letters, 101 (13): 130504, sep 2008. ISSN 00319007. 10.1103/​PhysRevLett.101.130504.

[28] Mario Szegedy. Quantum speed-up of Markov Chain based algorithms. In Proceedings – Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 32–41, 2004. 10.1109/​focs.2004.53.

[29] K. Temme, T. J. Osborne, K. G. Vollbrecht, D. Poulin, and F. Verstraete. Quantum Metropolis sampling. Nature, 471 (7336): 87–90, mar 2011. ISSN 00280836. 10.1038/​nature09770.

[30] Marija Vucelja. Lifting—A nonreversible Markov chain Monte Carlo algorithm. American Journal of Physics, 84 (12): 958–968, dec 2016. ISSN 0002-9505. 10.1119/​1.4961596.

[31] Man-Hong Yung and Alán Aspuru-Guzik. A quantum-quantum Metropolis algorithm. Proceedings of the National Academy of Sciences of the United States of America, 109 (3): 754–9, jan 2012. ISSN 1091-6490. 10.1073/​pnas.1111758109.

Cited by

[1] Jessica Lemieux, Guillaume Duclos-Cianci, David Sénéchal, and David Poulin, “Resource estimate for quantum many-body ground state preparation on a quantum computer”, arXiv:2006.04650.

The above citations are from SAO/NASA ADS (last updated successfully 2020-06-29 12:29:48). 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 2020-06-29 12:29:47: Could not fetch cited-by data for 10.22331/q-2020-06-29-287 from Crossref. This is normal if the DOI was registered recently.



Pursuing a career in quantum technologies




Quantum in the Summer

Scott, an A Level student at Lytchett Minster School, Poole, is currently studying Maths, Physics and Further Maths. He is also undertaking an Extended Project Qualification as an AS course and was tasked with writing a 5000 word dissertation on a topic of his choice, Scott chose to focus on “What are the uses of quantum entanglement for communication and data transfer”. During his time working on the dissertation, Scott has liaised regularly with Quantum Communications Hub Director, Tim Spiller. He hopes to go on to study at the University of Cambridge, Durham or York. We caught up with Scott to ask what sparked his interest in quantum physics, how he went about developing it within school and what his plans are for the future. Read on to see what he had to say.

“I believe one of the most beneficial qualities to have in life is curiosity, a thirst for knowledge and the ability to ask questions in order to fully understand an idea. To simply accept a fact you have been given as the truth, without ever considering why, is completely useless. How then are you meant to explain it to another person or apply it later in life, if you don’t first fully understand it yourself?

One of the most powerful words in the English language is “why”.  By asking it, not only do you further your understanding of a topic, you push the person you are speaking to to question the idea too. I’ve always had a natural fascination for this word, when I was younger, I would annoy my mum at every possible instant when I didn’t understand a concept. When I was 2, I asked her where the petrol in the car goes and why it needs refilling. She told me how the fuel enters the engine, is ignited, and then expands thus pushing the car forward. The next thing for me to ask was why the fuel expands, my Mum explained that this is to do with science, more specifically physics.

I noticed as I grew older that most ideas generally boiled down to some form of science if you ask why enough times.  I find the idea of working in scientific study so interesting, on a daily basis you are able to contribute to the general understanding of the world around us and get paid to do so.

I’ve recently developed a fondness of quantum physics. I find the idea of being able to understand and manipulate the smallest form of matter we are exposed to incredible. Matter behaves very differently on the quantum scale and being able to use these differences to our advantage can be very beneficial. It has already proved to be so with developments in quantum computing, encryption and many other fields.

At school, quantum technology research is touched upon, however, speaking to teachers and other professionals can help with extending knowledge and building relationships. Reaching out to Professors or researchers at Universities can also be a great way of getting into specific fields of sciences. They often tend to be very open to answering questions or helping with ideas if asked, especially with young students aspiring for careers in science. This can allow (especially aspiring scientists) an opportunity to speak to a professional and learn more complex topics that spark your interest at a younger age.

In the future I want to go on to study physics at Durham, Cambridge or York then specialise at postgraduate level. I currently would like to specialise in quantum physics or computing but I’m sure the initial Physics degree may spark interest somewhere else.

I would love to work in quantum computation technologies as I find the applications of such an abstract topic incredible. With companies like Google and IBM leading research on these topics I think it would be amazing to travel to America for a few years work on some of the most complex computers on the planet. ”


Continue Reading


Eleven risks of marrying a quantum information scientist




Some of you may have wondered whether I have a life. I do. He’s a computer scientist, and we got married earlier this month. 

Marrying a quantum information scientist comes with dangers not advertised in any Brides magazine (I assume; I’ve never opened a copy of Brides magazine). Never mind the perils of gathering together Auntie So-and-so and Cousin Such-and-such, who’ve quarreled since you were six; or spending tens of thousands of dollars on one day; or assembling two handfuls of humans during a pandemic. Beware the risks of marrying someone who unconsciously types “entropy” when trying to type “entry,” twice in a row.

1) She’ll introduce you to friends as “a classical computer scientist.” They’d assume, otherwise, that he does quantum computer science. Of course. Wouldn’t you?


2) The quantum punning will commence months before the wedding. One colleague wrote, “Many congratulations! Now you know the true meaning of entanglement.” Quantum particles can share entanglement. If you measure entangled particles, your outcomes can exhibit correlations stronger than any produceable by classical particles. As a card from another colleague read, “May you stay forever entangled, with no decoherence.”

I’d rather not dedicate much of a wedding article to decoherence, but suppose that two particles are maximally entangled (can generate the strongest correlations possible). Suppose that particle 2 heats up or suffers bombardment by other particles. The state of particle 2 decoheres as the entanglement between 1 and 2 frays. Equivalently, particle 2 entangles with its environment, and particle 2 can entangle only so much: The more entanglement 2 shares with the environment, the less entanglement 2 can share with 1. Physicists call entanglement—ba-duh-bummonogamous. 

The matron-of-honor toast featured another entanglement joke, as well as five more physics puns.1 (She isn’t a scientist, but she did her research.) She’ll be on Zoom till Thursday; try the virtual veal.


3) When you ask what sort of engagement ring she’d like, she’ll mention black diamonds. Experimentalists and engineers are building quantum computers from systems of many types, including diamond. Diamond consists of carbon atoms arranged in a lattice. Imagine expelling two neighboring carbon atoms and replacing one with a nitrogen atom. You’ll create a nitrogen-vacancy center whose electrons you can control with light. Such centers color the diamond black but let you process quantum information.

If I’d asked my fiancé for a quantum computer, we’d have had to wait 20 years to marry. He gave me an heirloom stone instead.


4) When a wedding-gown shopkeeper asks which sort of train she’d prefer, she’ll inquire about Maglevs. I dislike shopping, as the best man knows better than most people. In middle school, while our classmates spent their weekends at the mall, we stayed home and read books. But I filled out gown shops’ questionnaires. 

“They want to know what kinds of material I like,” I told the best man over the phone, “and what styles, and what type of train. I had to pick from four types of train. I didn’t even know there were four types of train!”

“Steam?” guessed the best man. “Diesel?”

His suggestions appealed to me as a quantum thermodynamicist. Thermodynamics is the physics of energy, which engines process. Quantum thermodynamicists study how quantum phenomena, such as entanglement, can improve engines. 

“Get the Maglev train,” the best man added. “Low emissions.”

“Ooh,” I said, “that’s superconducting.” Superconductors are quantum systems in which charge can flow forever, without dissipating. Labs at Yale, at IBM, and elsewhere are building quantum computers from superconductors. A superconductor consists of electrons that pair up with help from their positively charged surroundings—Cooper pairs. Separating Cooper-paired electrons requires an enormous amount of energy. What other type of train would better suit a wedding?

I set down my phone more at ease. Later, pandemic-era business closures constrained me to wearing a knee-length dress that I’d worn at graduations. I didn’t mind dodging the train.


5) When you ask what style of wedding dress she’ll wear, she’ll say that she likes her clothing as she likes her equations. Elegant in their simplicity.

6) You’ll plan your wedding for wedding season only because the rest of the year conflicts with more seminars, conferences, and colloquia. The quantum-information-theory conference of the year takes place in January. We wanted to visit Australia in late summer, and Germany in autumn, for conferences. A quantum-thermodynamics conference takes place early in the spring, and the academic year ends in May. Happy is the June bride; happier is the June bride who isn’t preparing a talk.

7) An MIT chaplain will marry you. Who else would sanctify the union of a physicist and a computer scientist?

8) You’ll acquire more in-laws than you bargained for. Biological parents more than suffice for most spouses. My husband has to contend with academic in-laws.


Academic in-laws of my husband’s attending the wedding via Zoom.

9) Your wedding can double as a conference. Had our wedding taken place in person, collaborations would have flourished during the cocktail hour. Papers would have followed; their acknowledgements sections would have nodded at the wedding; and I’d have requested copies of all manuscripts for our records—which might have included our wedding album.

10) You’ll have trouble identifying a honeymoon destination where she won’t be tempted to give a seminar. I thought that my then-fiancé would enjoy Vienna, but it boasts a quantum institute. So do Innsbruck and Delft. A colleague-friend works in Budapest, and I owe Berlin a professional visit. The list grew—or, rather, our options shrank. But he turned out not to mind my giving a seminar. The pandemic then cancelled our trip, so we’ll stay abroad for a week after some postpandemic European conference (hint hint).

11) Your wedding will feature on the blog of Caltech’s Institute for Quantum Information and Matter. Never mind The New York Times. Where else would you expect to find a quantum information physicist? I feel fortunate to have found someone with whom I wouldn’t rather be anywhere else.


1“I know that if Nicole picked him to stand by her side, he must be a FEYNMAN and not a BOZON.”


Continue Reading


On the Entanglement Cost of One-Shot Compression




Shima Bab Hadiashar and Ashwin Nayak

Department of Combinatorics and Optimization, and Institute for Quantum Computing, University of Waterloo, 200 University Ave. W., Waterloo, ON, N2L 3G1, Canada.

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


We revisit the task of visible compression of an ensemble of quantum states with entanglement assistance in the one-shot setting. The protocols achieving the best compression use many more qubits of shared entanglement than the number of qubits in the states in the ensemble. Other compression protocols, with potentially larger communication cost, have entanglement cost bounded by the number of qubits in the given states. This motivates the question as to whether entanglement is truly necessary for compression, and if so, how much of it is needed.
Motivated by questions in communication complexity, we lift certain restrictions that are placed on compression protocols in tasks such as state-splitting and channel simulation. We show that an ensemble of the form designed by Jain, Radhakrishnan, and Sen (ICALP’03) saturates the known bounds on the sum of communication and entanglement costs, even with the relaxed compression protocols we study.
The ensemble and the associated one-way communication protocol have several remarkable properties. The ensemble is incompressible by more than a constant number of qubits without shared entanglement, even when constant error is allowed. Moreover, in the presence of shared entanglement, the communication cost of compression can be arbitrarily smaller than the entanglement cost. The quantum information cost of the protocol can thus be arbitrarily smaller than the cost of compression without shared entanglement. The ensemble can also be used to show the impossibility of reducing, via compression, the shared entanglement used in two-party protocols for computing Boolean functions.

► BibTeX data

► References

[1] Anurag Anshu and Rahul Jain. Efficient methods for one-shot quantum communication. Technical Report arXiv:1809.07056 [quant-ph],, https:/​/​​abs/​1809.07056, September 2018.

[2] Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay, Ala Shayeghi, and Penghui Yao. New one shot quantum protocols with application to communication complexity. IEEE Transactions on Information Theory, 62 (12): 7566–7577, 2016. 10.1109/​TIT.2016.2616125.

[3] Anurag Anshu, Dave Touchette, Penghui Yao, and Nengkun Yu. Exponential separation of quantum communication and classical information. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 277–288, New York, NY, USA, 2017. ACM. ISBN 978-1-4503-4528-6. 10.1145/​3055399.3055401.

[4] Shima Bab Hadiashar, Ashwin Nayak, and Renato Renner. Communication complexity of one-shot remote state preparation. IEEE Transactions on Information Theory, 64 (7): 4709–4728, July 2018. 10.1109/​TIT.2018.2811509.

[5] Howard Barnum, Carlton M. Caves, Christopher A. Fuchs, Richard Jozsa, and Benjamin Schumacher. On quantum coding for ensembles of mixed states. Journal of Physics A: Mathematical and General, 34 (35): 6767–6785, August 2001. 10.1088/​0305-4470/​34/​35/​304.

[6] Charles H. Bennett, Igor Devetak, Aram W. Harrow, Peter W. Shor, and Andreas Winter. The quantum reverse Shannon theorem and resource tradeoffs for simulating quantum channels. IEEE Transactions on Information Theory, 60 (5): 2926–2959, May 2014. ISSN 0018-9448. 10.1109/​TIT.2014.2309968.

[7] Mario Berta, Matthias Christandl, and Renato Renner. The quantum reverse Shannon theorem based on one-shot information theory. Communications in Mathematical Physics, 306 (3): 579–615, August 2011. ISSN 1432-0916. 10.1007/​s00220-011-1309-7.

[8] Mario Berta, Matthias Christandl, and Dave Touchette. Smooth entropy bounds on one-shot quantum state redistribution. IEEE Transactions on Information Theory, 62 (3): 1425–1439, March 2016. 10.1109/​TIT.2016.2516006.

[9] Igor Devetak. Triangle of dualities between quantum communication protocols. Physical Review Letters, 97: 140503, Oct 2006. 10.1103/​PhysRevLett.97.140503.

[10] Igor Devetak and Jon Yard. Exact cost of redistributing multipartite quantum states. Physical Review Letters, 100 (230501), June 2008. 10.1103/​PhysRevLett.100.230501.

[11] Christopher A. Fuchs and Jeroen van de Graaf. Cryptographic distinguishability measures for quantum-mechanical states. IEEE Transactions on Information Theory, 45 (4): 1216–1227, May 1999. ISSN 1557-9654. 10.1109/​18.761271.

[12] Alexei Gilchrist, Nathan K. Langford, and Michael A. Nielsen. Distance measures to compare real and ideal quantum processes. Physical Review A, 71: 062310, Jun 2005. 10.1103/​PhysRevA.71.062310.

[13] Carl W. Helstrom. Detection theory and quantum mechanics. Information and Control, 10 (3): 254–291, 1967. 10.1016/​S0019-9958(67)90302-6.

[14] Alexander S. Holevo. An analogue of statistical decision theory and noncommutative probability theory. Trudy Moskovskogo Matematicheskogo Obshchestva, 26: 133–149, 1972.

[15] Michał Horodecki, Jonathan Oppenheim, and Andreas Winter. Partial quantum information. Nature, 436 (7051): 673–676, August 2005. 10.1038/​nature03909.

[16] Michał Horodecki, Jonathan Oppenheim, and Andreas Winter. Quantum state merging and negative information. Communications in Mathematical Physics, 269 (1): 107–136, January 2007. 10.1007/​s00220-006-0118-x.

[17] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. A direct sum theorem in communication complexity via message compression. In Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger, editors, Automata, Languages and Programming, volume 2719 of Lecture Notes in Computer Science, pages 300–315, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg. ISBN 978-3-540-45061-0. 10.1007/​3-540-45061-0_26.

[18] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. Prior entanglement, message compression and privacy in quantum communication. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pages 285–296. IEEE Computer Society, 2005. 10.1109/​CCC.2005.24.

[19] Rahul Jain, Pranab Sen, and Jaikumar Radhakrishnan. Optimal direct sum and privacy trade-off results for quantum and classical communication complexity. Technical Report arXiv:0807.1267v1 [cs.DC],, https:/​/​​abs/​0807.1267, July 2008.

[20] Zahra B. Khanian and Andreas Winter. Entanglement-assisted quantum data compression. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 1147–1151, 2019. 10.1109/​ISIT.2019.8849352.

[21] Troy Lee and Adi Shraibman. Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science, 3 (4): 263–399, 2009. ISSN 1551-305X. 10.1561/​0400000040.

[22] Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, and Scott Aaronson. Doubly infinite separation of quantum information and communication. Phys. Rev. A, 93: 012347, Jan 2016. 10.1103/​PhysRevA.93.012347.

[23] Zhicheng Luo and Igor Devetak. Channel simulation with quantum side information. IEEE Transactions on Information Theory, 55 (3): 1331–1342, March 2009. ISSN 0018-9448. 10.1109/​TIT.2008.2011424.

[24] Jiří Matoušek. Lectures on Discrete Geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag New York, 1st edition, 2002. ISBN 978-0-387-95373-1. 10.1007/​978-1-4613-0039-7.

[25] Elizabeth S. Meckes. The Random Matrix Theory of the Classical Compact Groups, volume 218 of Cambridge Tracts in Mathematics. Cambridge University Press, July 2019. 10.1017/​9781108303453.

[26] Vitali D. Milman and Gideon Schechtman. Asymptotic Theory of Finite Dimensional Normed Spaces, volume 1200 of Lecture notes in mathematics. Springer-Verlag Berlin Heidelberg, 1986. 10.1007/​978-3-540-38822-7.

[27] Marco Tomamichel, Roger Colbeck, and Renato Renner. Duality between smooth min- and max-entropies. IEEE Transactions on Information Theory, 56 (9): 4674–4681, September 2010. ISSN 0018-9448, 1557-9654. 10.1109/​TIT.2010.2054130.

[28] Dave Touchette. Quantum information complexity. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC ’15, pages 317–326, New York, NY, USA, 2015. ACM. ISBN 978-1-4503-3536-2. 10.1145/​2746539.2746613.

[29] John Watrous. The Theory of Quantum Information. Cambridge University Press, May 2018. 10.1017/​9781316848142.

[30] Jon T. Yard and Igor Devetak. Optimal quantum source coding with quantum side information at the encoder and decoder. IEEE Transactions on Information Theory, 55 (11): 5339–5351, November 2009. ISSN 0018-9448. 10.1109/​TIT.2009.2030494.

Cited by

Could not fetch Crossref cited-by data during last attempt 2020-06-25 09:55:43: Could not fetch cited-by data for 10.22331/q-2020-06-25-286 from Crossref. This is normal if the DOI was registered recently. On SAO/NASA ADS no data on citing works was found (last attempt 2020-06-25 09:55:44).


Continue Reading
Business Insider17 mins ago

Delta expects to see an 80% decline in travelers over the 4th of July weekend, and it shows how abysmal things are right now in the airline industry (DAL)

Business Insider18 mins ago

An app helping families save for college used this pitch deck to raise $9 million from investors like Anthos Capital and NBA all-star Baron Davis

Blockchain30 mins ago

Crypto Market Analysis: 1st July 2020

Business Insider31 mins ago

The Trump administration has hired a military contracting firm backed by Trump adviser Peter Thiel to build a virtual border wall

Payments31 mins ago

H.I.G. Carves Out Piece of Genuine Parts

Business Insider32 mins ago

19 TV shows Netflix canceled even though critics loved them

Business Insider33 mins ago

How much money TikTok influencers get paid to promote songs in their videos, according to music marketers, creators, and managers

Blockchain38 mins ago

KickEX New Deposit Contest; Make a deposit on the exchange and win 100 USDT!

Blockchain39 mins ago

Second Lawsuit Emerges: Why Are Hackers Targeting AT&T Crypto Investors?

Business Insider41 mins ago

Buying a house during the pandemic was a little tricky, but worth it for the rock-bottom rate we got on our mortgage

Business Insider43 mins ago

High-yield savings accounts aren’t earning much interest right now, but keeping my money at Ally Bank is still the smartest choice

Business Insider45 mins ago

Here are all the famous people Jeffrey Epstein was connected to

Blockchain45 mins ago

Bitcoin Breaks Below $9,000 as Sellers Invalidate Bullish Technical Pattern

Business Insider48 mins ago

Lemonade, a tech-driven insurance company, soars 132% in trading debut (LMND)

IOT48 mins ago

PiGirrl Zero w/ Audio #3DThursday #3DPrinting

IOT48 mins ago

A Massive Star Has Seemingly Vanished from Space With No Explanation

Business Insider49 mins ago

A Russian TV star denied holding racist views after she was fired as a brand ambassador to Audi after Instagram post controversy

Blockchain53 mins ago

Crypto Trading Woes: What They Are and How UpBots Solves Them

Payments54 mins ago

Centerbridge Sells KIK Piece to Voyant

Blockchain54 mins ago

Why Isn’t BCH Way More Popular on the Dark Web?

Business Insider1 hour ago

Leaked emails show Amazon is delaying Prime Day again to October as concerns grow that a new COVID-19 demand spike may hit supply chains (AMZN)

Business Insider1 hour ago

Former Republican presidential candidate Herman Cain is hospitalized with the coronavirus

Business Insider1 hour ago

Trump’s favorite trade scorecard worsened in May as exports hit lowest level since 2009

Business Insider1 hour ago

A free tool from the National Association of Insurance Commissioners can search for a life insurance policy after a loved one’s death

IOT1 hour ago

Review: Calculator Kit is Just a Few Hacks From Greatness

IOT1 hour ago

EYE on NPI – Alorium Evo M51 #EyeOnNPI #DigiKey #Adafruit @digikey @Adafruit @AloriumTech @Intel ​

IOT1 hour ago

Fursuit- or puppet-head base – version 71 – Toon dragon #3Dprinting #3DThursday

Covid191 hour ago

St Paul’s bomb plotter now denies she got cold feet, court hears

Blockchain1 hour ago

Twitter Adds Crypto Emoji for Binance, Following Bitcoin (BTC) and Coin (CRO)

Blockchain1 hour ago

Will This Year’s Third Quarter Be Negative for Bitcoin?

Mangoes healthy food to eat while high
Cannabis1 hour ago

Healthy foods to eat that can improve and extend your marijuana high

Gaming1 hour ago

Fortnite Fireworks Locations: Where To Light Fireworks For Captain America Challenge

Payments1 hour ago

Evolution Managers Backs Another New Manager

Private Equity1 hour ago

Dominus Capital raises up to $350m for Fund 3 but the target size for the fund looks to have dropped down to $525m

Blockchain1 hour ago

Bitcoin Price Prediction: BTC/USD Couldn’t Push Higher; Price Remains Below $9,200

Blockchain1 hour ago

Unknown Cybercrime Gang Holds Thousands of Databases For Ransom

Blockchain1 hour ago

Peter Schiff: Bitcoin HODLers Remain Delusional

Publications1 hour ago

EARN IT Act amendments transfer the fight over Section 230 to the states

Gaming1 hour ago

Fable Trademark Renewed Ahead Of Xbox Series X First-Party Showcase

Covid191 hour ago

David Starkey widely criticised for ‘slavery was not genocide’ remarks