Document Open Access Logo

Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-Calculus

Authors Alexandre Clément , Simon Perdrix

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.36.pdf
  • Filesize: 0.84 MB
  • 15 pages

Document Identifiers

Author Details

Alexandre Clément
  • Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
Simon Perdrix
  • Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

Funding

This work is funded by ANR-17-CE25-0009 SoftQPro, ANR-17-CE24-0035 VanQuTe, PIA-GDN/Quantex, and LUE/UOQ, the PEPR integrated project EPiQ ANR-22-PETQ-0007 part of Plan France 2030, and by "Investissements d'avenir" (ANR-15-IDEX-02) program of the French National Research Agency; the European Project NExt ApplicationS of Quantum Computing (NEASQC), funded by Horizon 2020 Program inside the call H2020-FETFLAG-2020-01 (Grant Agreement 951821), and the HPCQS European High-Performance Computing Joint Undertaking (JU) under grant agreement No 101018180.

Cite As Get BibTex

Alexandre Clément and Simon Perdrix. Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-Calculus. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.36

Abstract

Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. For instance, the complexity of implementing the permutation of some given unitary transformations can be strictly decreased by allowing coherent control, rather than using the standard quantum circuit model. In this paper, we address the problem of optimising the resources of coherently controlled quantum computations. We refine the PBS-calculus, a graphical language for coherent control which is inspired by quantum optics. In order to obtain a more resource-sensitive language, it manipulates abstract gates - that can be interpreted as queries to an oracle - and more importantly, it avoids the representation of useless wires by allowing unsaturated polarising beam splitters. Technically the language forms a coloured PROP. The language is equipped with an equational theory that we show to be sound, complete, and minimal.
Regarding resource optimisation, we introduce an efficient procedure to minimise the number of oracle queries of a given diagram. We also consider the problem of minimising both the number of oracle queries and the number of polarising beam splitters. We show that this optimisation problem is NP-hard in general, but introduce an efficient heuristic that produces optimal diagrams when at most one query to each oracle is required.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
  • Theory of computation → Axiomatic semantics
  • Theory of computation → Categorical semantics
Keywords
  • Quantum computing
  • Graphical language
  • Coherent control
  • Completeness
  • Resource optimisation
  • NP-hardness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Alastair A. Abbott, Julian Wechs, Dominic Horsman, Mehdi Mhalla, and Cyril Branciard. Communication through coherent control of quantum channels. Quantum, 4:333, September 2020. URL: https://doi.org/10.22331/q-2020-09-24-333.
  2. Thorsten Altenkirch and Jonathan Grattage. A functional quantum programming language. In 20th Annual IEEE Symposium on Logic in Computer Science (LICS'05), pages 249-258. IEEE, 2005. Google Scholar
  3. Matthew Amy, Dmitri Maslov, and Michele Mosca. Polynomial-time T-depth optimization of Clifford+T circuits via matroid partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 33(10):1476-1489, 2014. Google Scholar
  4. Mateus Araújo, Fabio Costa, and Časlav Brukner. Computational advantage from quantum-controlled ordering of gates. Physical Review Letters, 113(25):250402, 2014. URL: https://doi.org/10.1103/PhysRevLett.113.250402.
  5. Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron. Addressable quantum gates. arXiv preprint, 2021. URL: http://arxiv.org/abs/2109.08050.
  6. Costin Badescu and Prakash Panangaden. Quantum alternation: Prospects and problems. In Chris Heunen, Peter Selinger, and Jamie Vicary, editors, Proceedings 12th International Workshop on Quantum Physics and Logic, QPL 2015, Oxford, UK, July 15-17, 2015, volume 195 of EPTCS, pages 33-42, 2015. URL: https://doi.org/10.4204/EPTCS.195.3.
  7. Cyril Branciard, Alexandre Clément, Mehdi Mhalla, and Simon Perdrix. Coherent control and distinguishability of quantum channels via PBS-diagrams. In Filippo Bonchi and Simon J. Puglisi, editors, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volume 202 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1-22:20, Dagstuhl, Germany, August 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.MFCS.2021.22.
  8. Alberto Caprara. Sorting permutations by reversals and Eulerian cycle decompositions. SIAM Journal on Discrete Mathematics, 12(1):91-110, 1999. URL: https://doi.org/10.1137/S089548019731994X.
  9. Giulio Chiribella. Perfect discrimination of no-signalling channels via quantum superposition of causal structures. Physical Review A, 86(4):040301, 2012. URL: https://doi.org/10.1103/PhysRevA.86.040301.
  10. Giulio Chiribella, Giacomo Mauro D'Ariano, Paolo Perinotti, and Benoît Valiron. Quantum computations without definite causal structure. Physical Review A, 88:022318, August 2013. URL: https://doi.org/10.1103/PhysRevA.88.022318.
  11. Alexandre Clément, Nicolas Heurtel, Shane Mansfield, Simon Perdrix, and Benoît Valiron. LOv-calculus: A graphical language for linear optical quantum circuits. Accepted at MFCS'22, 2022. URL: http://arxiv.org/abs/2204.11787.
  12. Alexandre Clément and Simon Perdrix. PBS-calculus: A graphical language for coherent control of quantum computations. In Javier Esparza and Daniel Kráľ, editors, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 24:1-24:14, Dagstuhl, Germany, August 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.24.
  13. Alexandre Clément and Simon Perdrix. Minimising resources of coherently controlled quantum computations, 2022. URL: https://doi.org/10.48550/ARXIV.2202.05260.
  14. Timoteo Colnaghi, Giacomo Mauro D'Ariano, Stefano Facchini, and Paolo Perinotti. Quantum computation with programmable connections between gates. Physics Letters A, 376(45):2940-2943, 2012. URL: https://doi.org/10.1016/j.physleta.2012.08.028.
  15. Alejandro Díaz-Caro, Mauricio Guillermo, Alexandre Miquel, and Benoît Valiron. Realizability in the unitary sphere. In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-13. IEEE, 2019. Google Scholar
  16. Gilles Dowek and Pablo Arrighi. Lineal: A linear-algebraic lambda-calculus. Logical Methods in Computer Science, 13, 2017. Google Scholar
  17. Daniel Ebler, Sina Salek, and Giulio Chiribella. Enhanced communication with the assistance of indefinite causal order. Physical Review Letters, 120(12):120502, March 2018. URL: https://doi.org/10.1103/PhysRevLett.120.120502.
  18. Stefano Facchini and Simon Perdrix. Quantum circuits for the unitary permutation problem. In International Conference on Theory and Applications of Models of Computation, pages 324-331. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-17142-5_28.
  19. Adrien Feix, Mateus Araújo, and Časlav Brukner. Quantum superposition of the order of parties as a communication resource. Physical Review A, 92(5):052326, 2015. URL: https://doi.org/10.1103/PhysRevA.92.052326.
  20. Philippe Allard Guérin, Adrien Feix, Mateus Araújo, and Časlav Brukner. Exponential communication complexity advantage from quantum superposition of the direction of communication. Physical Review Letters, 117(10):100502, 2016. URL: https://doi.org/10.1103/PhysRevLett.117.100502.
  21. Lucien Hardy. Probability theories with dynamic causal structure: a new framework for quantum gravity. arXiv preprint gr-qc/0509120, 2005. Google Scholar
  22. Masahito Hasegawa, Martin Hofmann, and Gordon Plotkin. Finite dimensional vector spaces are complete for traced symmetric monoidal categories. In Pillars of computer science, pages 367-385. Springer, 2008. Google Scholar
  23. Vadym Kliuchnikov and Dmitri Maslov. Optimization of Clifford circuits. Physical Review A, 88(5):052307, 2013. Google Scholar
  24. Saunders MacLane. Categorical algebra. Bulletin of the American Mathematical Society, 71(1):40-106, 1965. Google Scholar
  25. Yunseong Nam, Neil J. Ross, Yuan Su, Andrew M. Childs, and Dmitri Maslov. Automated optimization of large quantum circuits with continuous parameters. npj Quantum Information, 4(1):1-12, 2018. Google Scholar
  26. Ognyan Oreshkov, Fabio Costa, and Časlav Brukner. Quantum correlations with no causal order. Nature communications, 3(1):1-8, 2012. Google Scholar
  27. Martin J. Renner and Časlav Brukner. Reassessing the computational advantage of quantum-controlled ordering of gates. Physical Review Research, 3(4):043012, 2021. Google Scholar
  28. Peter Selinger. Finite dimensional hilbert spaces are complete for dagger compact closed categories. Electronic Notes in Theoretical Computer Science, 270(1):113-119, 2011. Google Scholar
  29. Augustin Vanrietvelde, Hlér Kristjánsson, and Jonathan Barrett. Routed quantum circuits. Quantum, 5:503, 2021. Google Scholar
  30. Julian Wechs, Hippolyte Dourdent, Alastair A. Abbott, and Cyril Branciard. Quantum circuits with classical versus quantum control of causal order. arXiv preprint, 2021. URL: http://arxiv.org/abs/2101.08796.
  31. Matt Wilson and Giulio Chiribella. A diagrammatic approach to information transmission in generalised switches. arXiv preprint, 2020. URL: http://arxiv.org/abs/2003.08224.
  32. Mingsheng Ying, Nengkun Yu, and Yuan Feng. Defining quantum control flow. arXiv preprint, 2012. URL: http://arxiv.org/abs/1209.4379.
  33. Magdalena Zych, Fabio Costa, Igor Pikovski, and Časlav Brukner. Bell’s theorem for temporal order. Nature communications, 10(1):1-10, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact