Document

Track A: Algorithms, Complexity and Games

**Published in:** LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

We present an efficient quantum algorithm for simulating the dynamics of Markovian open quantum systems. The performance of our algorithm is similar to the previous state-of-the-art quantum algorithm, i.e., it scales linearly in evolution time and poly-logarithmically in inverse precision. However, our algorithm is conceptually cleaner, and it only uses simple quantum primitives without compressed encoding. Our approach is based on a novel mathematical treatment of the evolution map, which involves a higher-order series expansion based on Duhamel’s principle and approximating multiple integrals using scaled Gaussian quadrature. Our method easily generalizes to simulating quantum dynamics with time-dependent Lindbladians. Furthermore, our method of approximating multiple integrals using scaled Gaussian quadrature could potentially be used to produce a more efficient approximation of time-ordered integrals, and therefore can simplify existing quantum algorithms for simulating time-dependent Hamiltonians based on a truncated Dyson series.

Xiantao Li and Chunhao Wang. Simulating Markovian Open Quantum Systems Using Higher-Order Series Expansion. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 87:1-87:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ICALP.2023.87, author = {Li, Xiantao and Wang, Chunhao}, title = {{Simulating Markovian Open Quantum Systems Using Higher-Order Series Expansion}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {87:1--87:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.87}, URN = {urn:nbn:de:0030-drops-181395}, doi = {10.4230/LIPIcs.ICALP.2023.87}, annote = {Keywords: Quantum algorithms, open quantum systems, Lindblad simulation} }

Document

**Published in:** LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

We present two efficient classical analogues of the quantum matrix inversion algorithm [Harrow et al., 2009] for low-rank matrices. Inspired by recent work of Tang [Tang, 2019], assuming length-square sampling access to input data, we implement the pseudoinverse of a low-rank matrix allowing us to sample from the solution to the problem Ax = b using fast sampling techniques. We construct implicit descriptions of the pseudo-inverse by finding approximate singular value decomposition of A via subsampling, then inverting the singular values. In principle, our approaches can also be used to apply any desired "smooth" function to the singular values. Since many quantum algorithms can be expressed as a singular value transformation problem [András Gilyén et al., 2019], our results indicate that more low-rank quantum algorithms can be effectively "dequantised" into classical length-square sampling algorithms.

Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, and Chunhao Wang. Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 47:1-47:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chia_et_al:LIPIcs.ISAAC.2020.47, author = {Chia, Nai-Hui and Gily\'{e}n, Andr\'{a}s and Lin, Han-Hsuan and Lloyd, Seth and Tang, Ewin and Wang, Chunhao}, title = {{Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {47:1--47:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.47}, URN = {urn:nbn:de:0030-drops-133916}, doi = {10.4230/LIPIcs.ISAAC.2020.47}, annote = {Keywords: sublinear algorithms, quantum-inspired, regression, importance sampling, quantum machine learning} }

Document

**Published in:** LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. In this paper, we present a proof-of-principle sublinear-time algorithm for solving SDPs with low-rank constraints; specifically, given an SDP with m constraint matrices, each of dimension n and rank r, our algorithm can compute any entry and efficient descriptions of the spectral decomposition of the solution matrix. The algorithm runs in time O(m⋅poly(log n,r,1/ε)) given access to a sampling-based low-overhead data structure for the constraint matrices, where ε is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application.
Technically, our approach aligns with 1) SDP solvers based on the matrix multiplicative weight (MMW) framework by Arora and Kale [TOC '12]; 2) sampling-based dequantizing framework pioneered by Tang [STOC '19]. In order to compute the matrix exponential required in the MMW framework, we introduce two new techniques that may be of independent interest:
- Weighted sampling: assuming sampling access to each individual constraint matrix A₁,…,A_τ, we propose a procedure that gives a good approximation of A = A₁+⋯+A_τ.
- Symmetric approximation: we propose a sampling procedure that gives the spectral decomposition of a low-rank Hermitian matrix A. To the best of our knowledge, this is the first sampling-based algorithm for spectral decomposition, as previous works only give singular values and vectors.

Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang. Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 23:1-23:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chia_et_al:LIPIcs.MFCS.2020.23, author = {Chia, Nai-Hui and Li, Tongyang and Lin, Han-Hsuan and Wang, Chunhao}, title = {{Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {23:1--23:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.23}, URN = {urn:nbn:de:0030-drops-126919}, doi = {10.4230/LIPIcs.MFCS.2020.23}, annote = {Keywords: Spectral decomposition, Semi-definite programming, Quantum-inspired algorithm, Sublinear algorithm} }

Document

**Published in:** LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

The closest pair problem is a fundamental problem of computational geometry: given a set of n points in a d-dimensional space, find a pair with the smallest distance. A classical algorithm taught in introductory courses solves this problem in O(n log n) time in constant dimensions (i.e., when d = O(1)). This paper asks and answers the question of the problem’s quantum time complexity. Specifically, we give an Õ(n^(2/3)) algorithm in constant dimensions, which is optimal up to a polylogarithmic factor by the lower bound on the quantum query complexity of element distinctness. The key to our algorithm is an efficient history-independent data structure that supports quantum interference.
In polylog(n) dimensions, no known quantum algorithms perform better than brute force search, with a quadratic speedup provided by Grover’s algorithm. To give evidence that the quadratic speedup is nearly optimal, we initiate the study of quantum fine-grained complexity and introduce the Quantum Strong Exponential Time Hypothesis (QSETH), which is based on the assumption that Grover’s algorithm is optimal for CNF-SAT when the clause width is large. We show that the naïve Grover approach to closest pair in higher dimensions is optimal up to an n^o(1) factor unless QSETH is false. We also study the bichromatic closest pair problem and the orthogonal vectors problem, with broadly similar results.

Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, and Ruizhe Zhang. On the Quantum Complexity of Closest Pair and Related Problems. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 16:1-16:43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aaronson_et_al:LIPIcs.CCC.2020.16, author = {Aaronson, Scott and Chia, Nai-Hui and Lin, Han-Hsuan and Wang, Chunhao and Zhang, Ruizhe}, title = {{On the Quantum Complexity of Closest Pair and Related Problems}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {16:1--16:43}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.16}, URN = {urn:nbn:de:0030-drops-125681}, doi = {10.4230/LIPIcs.CCC.2020.16}, annote = {Keywords: Closest pair, Quantum computing, Quantum fine grained reduction, Quantum strong exponential time hypothesis, Fine grained complexity} }

Document

**Published in:** LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

We consider the natural generalization of the Schrodinger equation to Markovian open system dynamics: the so-called the Lindblad equation. We give a quantum algorithm for simulating the evolution of an n-qubit system for time t within precision epsilon. If the Lindbladian consists of poly(n) operators that can each be expressed as a linear combination of poly(n) tensor products of Pauli operators then the gate cost of our algorithm is O(t polylog(t/epsilon) poly(n)). We also obtain similar bounds for the cases where the Lindbladian consists of local operators, and where the Lindbladian consists of sparse operators. This is remarkable in light of evidence that we provide indicating that the above efficiency is impossible to attain by first expressing Lindblad evolution as Schrodinger evolution on a larger system and tracing out the ancillary system: the cost of such a reduction incurs an efficiency overhead of O(t^2/epsilon) even before the Hamiltonian evolution simulation begins. Instead, the approach of our algorithm is to use a novel variation of the "linear combinations of unitaries" construction that pertains to channels.

Richard Cleve and Chunhao Wang. Efficient Quantum Algorithms for Simulating Lindblad Evolution. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 17:1-17:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cleve_et_al:LIPIcs.ICALP.2017.17, author = {Cleve, Richard and Wang, Chunhao}, title = {{Efficient Quantum Algorithms for Simulating Lindblad Evolution}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {17:1--17:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.17}, URN = {urn:nbn:de:0030-drops-74776}, doi = {10.4230/LIPIcs.ICALP.2017.17}, annote = {Keywords: quantum algorithms, open quantum systems, Lindblad simulation} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail