15 Search Results for "Apers, Simon"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.110
Optimal Two-Round Communication Lower Bound for Graph Connectivity via Pointer Chasing

Authors: Jaikumar Radhakrishnan, Chaitanya Reddy, and Rakesh Venkat

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We consider the communication complexity of the graph connectivity problem, where the edges of an n-vertex undirected graph G are distributed between two parties Alice and Bob, who are then required to communicate to determine if G is connected. We show that in any randomized protocol with two-rounds of communication, Alice and Bob must exchange Ω(nlog n) bits; such a lower bound for one-round protocols was shown by Sun and Woodruff (APPROX/RANDOM 2015). A one-round deterministic protocol, where Alice sends O(n log n) bits and Bob determines the answer, was observed by Hajnal, Maass and Turan (STOC 1988); they also showed a matching lower bound of Ω(n log n) bits for deterministic protocols with unbounded rounds of communication. For randomized protocols, a reduction from the set disjointness problem due to Babai, Frankl and Simon (FOCS 1986) implies a randomized lower bound of Ω(n) even with unbounded rounds of communication. Whether this lower bound can be improved to Ω(n log n) has been an outstanding open question, whose algorithmic implications were recently emphasized by Apers, Efron, Gawrychowski, Lee, Mukopadhyay and Nanongkai (FOCS 2022). Our lower bound for randomized two-round protocols is based on a reduction from a restricted version of the two-player pointer chasing problem originally studied by Papadimitriou and Sipser (JCSS 1984). Using this reduction, we show an ω(n) lower bounds on graph connectivity for any constant number of rounds by extending deterministic lower bounds shown by Ponzio, Radhakrishnan and Venkatesh (JCSS 2001) to the randomized setting.
Cite as

Jaikumar Radhakrishnan, Chaitanya Reddy, and Rakesh Venkat. Optimal Two-Round Communication Lower Bound for Graph Connectivity via Pointer Chasing. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 110:1-110:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{radhakrishnan_et_al:LIPIcs.ITCS.2026.110,
  author =	{Radhakrishnan, Jaikumar and Reddy, Chaitanya and Venkat, Rakesh},
  title =	{{Optimal Two-Round Communication Lower Bound for Graph Connectivity via Pointer Chasing}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{110:1--110:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  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.ITCS.2026.110},
  URN =		{urn:nbn:de:0030-drops-253974},
  doi =		{10.4230/LIPIcs.ITCS.2026.110},
  annote =	{Keywords: Communication complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.51
Quantum Approximate k-Minimum Finding

Authors: Minbo Gao, Zhengfeng Ji, and Qisheng Wang

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Quantum k-minimum finding is a fundamental subroutine with numerous applications in combinatorial problems and machine learning. Previous approaches typically assume oracle access to exact function values, making it challenging to integrate this subroutine with other quantum algorithms. In this paper, we propose an (almost) optimal quantum k-minimum finding algorithm that works with approximate values for all k ≥ 1, extending a result of van Apeldoorn, Gilyén, Gribling, and de Wolf (FOCS 2017) for k = 1. As practical applications, we present efficient quantum algorithms for identifying the k smallest expectation values among multiple observables and for determining the k lowest ground state energies of a Hamiltonian with a known eigenbasis.
Cite as

Minbo Gao, Zhengfeng Ji, and Qisheng Wang. Quantum Approximate k-Minimum Finding. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.ESA.2025.51,
  author =	{Gao, Minbo and Ji, Zhengfeng and Wang, Qisheng},
  title =	{{Quantum Approximate k-Minimum Finding}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{51:1--51:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.51},
  URN =		{urn:nbn:de:0030-drops-245192},
  doi =		{10.4230/LIPIcs.ESA.2025.51},
  annote =	{Keywords: Quantum Computing, Quantum Algorithms, Quantum Minimum Finding}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.100
Cut-Query Algorithms with Few Rounds

Authors: Yotam Kenneth-Mordoch and Robert Krauthgamer

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
In the cut-query model, the algorithm can access the input graph G = (V,E) only via cut queries that report, given a set S ⊆ V, the total weight of edges crossing the cut between S and V⧵ S. This model was introduced by Rubinstein, Schramm and Weinberg [ITCS'18] and its investigation has so far focused on the number of queries needed to solve optimization problems, such as global minimum cut. We turn attention to the round complexity of cut-query algorithms, and show that several classical problems can be solved in this model with only a constant number of rounds. Our main results are algorithms for finding a minimum cut in a graph, that offer different tradeoffs between round complexity and query complexity, where n = |V| and δ(G) denotes the minimum degree of G: (i) Õ(n^{4/3}) cut queries in two rounds in unweighted graphs; (ii) Õ(rn^{1+1/r}/δ(G)^{1/r}) queries in 2r+1 rounds for any integer r ≥ 1 again in unweighted graphs; and (iii) Õ(rn^{1+(1+log_n W)/r}) queries in 4r+3 rounds for any r ≥ 1 in weighted graphs. We also provide algorithms that find a minimum (s,t)-cut and approximate the maximum cut in a few rounds.
Cite as

Yotam Kenneth-Mordoch and Robert Krauthgamer. Cut-Query Algorithms with Few Rounds. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 100:1-100:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kennethmordoch_et_al:LIPIcs.ESA.2025.100,
  author =	{Kenneth-Mordoch, Yotam and Krauthgamer, Robert},
  title =	{{Cut-Query Algorithms with Few Rounds}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{100:1--100:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.100},
  URN =		{urn:nbn:de:0030-drops-245692},
  doi =		{10.4230/LIPIcs.ESA.2025.100},
  annote =	{Keywords: Cut Queries, Round Complexity, Submodular Optimization}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.32
Quantum Property Testing in Sparse Directed Graphs

Authors: Simon Apers, Frédéric Magniez, Sayantan Sen, and Dániel Szabó

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the outgoing edges of a vertex. In the classical unidirectional model, the problem of testing k-star-freeness, and more generally k-source-subgraph-freeness, is almost maximally hard for large k. We prove that this problem has almost quadratic advantage in the quantum setting. Moreover, we show that this advantage is nearly tight, by showing a quantum lower bound using the method of dual polynomials on an intermediate problem for a new, property testing version of the k-collision problem that was not studied before. To illustrate that not all problems in graph property testing admit such a quantum speedup, we consider the problem of 3-colorability in the related undirected bounded-degree model, when graphs are now undirected. This problem is maximally hard to test classically, and we show that also quantumly it requires a linear number of queries.
Cite as

Simon Apers, Frédéric Magniez, Sayantan Sen, and Dániel Szabó. Quantum Property Testing in Sparse Directed Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 32:1-32:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.APPROX/RANDOM.2025.32,
  author =	{Apers, Simon and Magniez, Fr\'{e}d\'{e}ric and Sen, Sayantan and Szab\'{o}, D\'{a}niel},
  title =	{{Quantum Property Testing in Sparse Directed Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{32:1--32:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.32},
  URN =		{urn:nbn:de:0030-drops-243987},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.32},
  annote =	{Keywords: property testing, quantum computing, bounded-degree directed graphs, dual polynomial method, collision finding}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.18
Directed st-Connectivity with Few Paths Is in Quantum Logspace

Authors: Simon Apers and Roman Edenhofer

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
We present a BQSPACE(O(log n))-procedure to count st-paths on directed graphs for which we are promised that there are at most polynomially many paths starting in s and polynomially many paths ending in t. For comparison, the best known classical upper bound in this case just to decide st-connectivity is DSPACE(O(log² n/ log log n)). The result establishes a new relationship between BQL and unambiguity and fewness subclasses of NL. Further, we also show how to recognize directed graphs with at most polynomially many paths between any two nodes in BQSPACE(O(log n)). This yields the first natural candidate for a language separating BQL from 𝖫 and BPL. Until now, all candidates potentially separating these classes were inherently promise problems.
Cite as

Simon Apers and Roman Edenhofer. Directed st-Connectivity with Few Paths Is in Quantum Logspace. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.CCC.2025.18,
  author =	{Apers, Simon and Edenhofer, Roman},
  title =	{{Directed st-Connectivity with Few Paths Is in Quantum Logspace}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.18},
  URN =		{urn:nbn:de:0030-drops-237128},
  doi =		{10.4230/LIPIcs.CCC.2025.18},
  annote =	{Keywords: Quantum computation, Space-bounded complexity classes, Graph connectivity, Unambiguous computation, Random walks}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.61
How to Compute the Volume in Low Dimension?

Authors: Arjan Cornelissen, Simon Apers, and Sander Gribling

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Estimating the volume of a convex body is a canonical problem in theoretical computer science. Its study has led to major advances in randomized algorithms, Markov chain theory, and computational geometry. In particular, determining the query complexity of volume estimation to a membership oracle has been a longstanding open question. Most of the previous work focuses on the high-dimensional limit. In this work, we tightly characterize the deterministic, randomized and quantum query complexity of this problem in the high-precision limit, i.e., when the dimension is constant.
Cite as

Arjan Cornelissen, Simon Apers, and Sander Gribling. How to Compute the Volume in Low Dimension?. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 61:1-61:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cornelissen_et_al:LIPIcs.ICALP.2025.61,
  author =	{Cornelissen, Arjan and Apers, Simon and Gribling, Sander},
  title =	{{How to Compute the Volume in Low Dimension?}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{61:1--61:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.61},
  URN =		{urn:nbn:de:0030-drops-234381},
  doi =		{10.4230/LIPIcs.ICALP.2025.61},
  annote =	{Keywords: Query complexity, computational geometry, quantum computing, volume estimation, high-precision limit}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.13
Quantum Speedup for Sampling Random Spanning Trees

Authors: Simon Apers, Minbo Gao, Zhengfeng Ji, and Chenghua Liu

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We present a quantum algorithm for sampling random spanning trees from a weighted graph in Õ(√{mn}) time, where n and m denote the number of vertices and edges, respectively. Our algorithm has sublinear runtime for dense graphs and achieves a quantum speedup over the best-known classical algorithm, which runs in Õ(m) time. The approach carefully combines, on one hand, a classical method based on "large-step" random walks for reduced mixing time and, on the other hand, quantum algorithmic techniques, including quantum graph sparsification and a sampling-without-replacement variant of Hamoudi’s multiple-state preparation. We also establish a matching lower bound, proving the optimality of our algorithm up to polylogarithmic factors. These results highlight the potential of quantum computing in accelerating fundamental graph sampling problems.
Cite as

Simon Apers, Minbo Gao, Zhengfeng Ji, and Chenghua Liu. Quantum Speedup for Sampling Random Spanning Trees. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.ICALP.2025.13,
  author =	{Apers, Simon and Gao, Minbo and Ji, Zhengfeng and Liu, Chenghua},
  title =	{{Quantum Speedup for Sampling Random Spanning Trees}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{13:1--13:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.13},
  URN =		{urn:nbn:de:0030-drops-233907},
  doi =		{10.4230/LIPIcs.ICALP.2025.13},
  annote =	{Keywords: Quantum Computing, Quantum Algorithms, Random Spanning Trees}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.54
Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer

Authors: Stacey Jeffery and Galina Pass

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We introduce an object called a subspace graph that formalizes the technique of multidimensional quantum walks. Composing subspace graphs allows one to seamlessly combine quantum and classical reasoning, keeping a classical structure in mind, while abstracting quantum parts into subgraphs with simple boundaries as needed. As an example, we show how to combine a switching network with arbitrary quantum subroutines, to compute a composed function. As another application, we give a time-efficient implementation of quantum Divide & Conquer when the sub-problems are combined via a Boolean formula. We use this to quadratically speed up Savitch’s algorithm for directed st-connectivity.
Cite as

Stacey Jeffery and Galina Pass. Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jeffery_et_al:LIPIcs.STACS.2025.54,
  author =	{Jeffery, Stacey and Pass, Galina},
  title =	{{Multidimensional Quantum Walks, Recursion, and Quantum Divide \& Conquer}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{54:1--54:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.54},
  URN =		{urn:nbn:de:0030-drops-228791},
  doi =		{10.4230/LIPIcs.STACS.2025.54},
  annote =	{Keywords: Quantum Divide \& Conquer, Time-Efficient, Subspace Graphs, Quantum Walks, Switching Networks, Directed st-Connectivity}
}
Document
DOI: 10.4230/LIPIcs.TQC.2024.8
(Quantum) Complexity of Testing Signed Graph Clusterability

Authors: Kuo-Chin Chen, Simon Apers, and Min-Hsiu Hsieh

Published in: LIPIcs, Volume 310, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)

Abstract
This study examines clusterability testing for a signed graph in the bounded-degree model. Our contributions are two-fold. First, we provide a quantum algorithm with query complexity Õ(N^{1/3}) for testing clusterability, which yields a polynomial speedup over the best classical clusterability tester known [Adriaens and Apers, 2023]. Second, we prove an Ω̃(√N) classical query lower bound for testing clusterability, which nearly matches the upper bound from [Adriaens and Apers, 2023]. This settles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.
Cite as

Kuo-Chin Chen, Simon Apers, and Min-Hsiu Hsieh. (Quantum) Complexity of Testing Signed Graph Clusterability. In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 310, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.TQC.2024.8,
  author =	{Chen, Kuo-Chin and Apers, Simon and Hsieh, Min-Hsiu},
  title =	{{(Quantum) Complexity of Testing Signed Graph Clusterability}},
  booktitle =	{19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-328-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{310},
  editor =	{Magniez, Fr\'{e}d\'{e}ric and Grilo, Alex Bredariol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2024.8},
  URN =		{urn:nbn:de:0030-drops-206786},
  doi =		{10.4230/LIPIcs.TQC.2024.8},
  annote =	{Keywords: Quantum Algorithm, classical Query lower Bound, Graph Property testing}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.10
(No) Quantum Space-Time Tradeoff for USTCON

Authors: Simon Apers, Stacey Jeffery, Galina Pass, and Michael Walter

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Undirected st-connectivity is important both for its applications in network problems, and for its theoretical connections with logspace complexity. Classically, a long line of work led to a time-space tradeoff of T = Õ(n²/S) for any S such that S = Ω(log(n)) and S = O(n²/m). Surprisingly, we show that quantumly there is no nontrivial time-space tradeoff: there is a quantum algorithm that achieves both optimal time Õ(n) and space O(log(n)) simultaneously. This improves on previous results, which required either O(log(n)) space and Õ(n^{1.5}) time, or Õ(n) space and time. To complement this, we show that there is a nontrivial time-space tradeoff when given a lower bound on the spectral gap of a corresponding random walk.
Cite as

Simon Apers, Stacey Jeffery, Galina Pass, and Michael Walter. (No) Quantum Space-Time Tradeoff for USTCON. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.ESA.2023.10,
  author =	{Apers, Simon and Jeffery, Stacey and Pass, Galina and Walter, Michael},
  title =	{{(No) Quantum Space-Time Tradeoff for USTCON}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.10},
  URN =		{urn:nbn:de:0030-drops-186636},
  doi =		{10.4230/LIPIcs.ESA.2023.10},
  annote =	{Keywords: Undirected st-connectivity, quantum walks, time-space tradeoff}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.32
Finding the KT Partition of a Weighted Graph in Near-Linear Time

Authors: Simon Apers, Paweł Gawrychowski, and Troy Lee

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
In a breakthrough work, Kawarabayashi and Thorup (J. ACM'19) gave a near-linear time deterministic algorithm to compute the weight of a minimum cut in a simple graph G = (V,E). A key component of this algorithm is finding the (1+ε)-KT partition of G, the coarsest partition {P_1, …, P_k} of V such that for every non-trivial (1+ε)-near minimum cut with sides {S, ̄{S}} it holds that P_i is contained in either S or ̄{S}, for i = 1, …, k. In this work we give a near-linear time randomized algorithm to find the (1+ε)-KT partition of a weighted graph. Our algorithm is quite different from that of Kawarabayashi and Thorup and builds on Karger’s framework of tree-respecting cuts (J. ACM'00). We describe a number of applications of the algorithm. (i) The algorithm makes progress towards a more efficient algorithm for constructing the polygon representation of the set of near-minimum cuts in a graph. This is a generalization of the cactus representation, and was initially described by Benczúr (FOCS'95). (ii) We improve the time complexity of a recent quantum algorithm for minimum cut in a simple graph in the adjacency list model from Õ(n^{3/2}) to Õ(√{mn}), when the graph has n vertices and m edges. (iii) We describe a new type of randomized algorithm for minimum cut in simple graphs with complexity 𝒪(m + n log⁶ n). For graphs that are not too sparse, this matches the complexity of the current best 𝒪(m + n log² n) algorithm which uses a different approach based on random contractions. The key technical contribution of our work is the following. Given a weighted graph G with m edges and a spanning tree T of G, consider the graph H whose nodes are the edges of T, and where there is an edge between two nodes of H iff the corresponding 2-respecting cut of T is a non-trivial near-minimum cut of G. We give a 𝒪(m log⁴ n) time deterministic algorithm to compute a spanning forest of H.
Cite as

Simon Apers, Paweł Gawrychowski, and Troy Lee. Finding the KT Partition of a Weighted Graph in Near-Linear Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.APPROX/RANDOM.2022.32,
  author =	{Apers, Simon and Gawrychowski, Pawe{\l} and Lee, Troy},
  title =	{{Finding the KT Partition of a Weighted Graph in Near-Linear Time}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{32:1--32:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.32},
  URN =		{urn:nbn:de:0030-drops-171544},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.32},
  annote =	{Keywords: Graph theory}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.28
Quantum Complexity of Minimum Cut

Authors: Simon Apers and Troy Lee

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
The minimum cut problem in an undirected and weighted graph G is to find the minimum total weight of a set of edges whose removal disconnects G. We completely characterize the quantum query and time complexity of the minimum cut problem in the adjacency matrix model. If G has n vertices and edge weights at least 1 and at most τ, we give a quantum algorithm to solve the minimum cut problem using Õ(n^{3/2}√{τ}) queries and time. Moreover, for every integer 1 ≤ τ ≤ n we give an example of a graph G with edge weights 1 and τ such that solving the minimum cut problem on G requires Ω(n^{3/2}√{τ}) queries to the adjacency matrix of G. These results contrast with the classical randomized case where Ω(n²) queries to the adjacency matrix are needed in the worst case even to decide if an unweighted graph is connected or not. In the adjacency array model, when G has m edges the classical randomized complexity of the minimum cut problem is ̃ Θ(m). We show that the quantum query and time complexity are Õ(√{mnτ}) and Õ(√{mnτ} + n^{3/2}), respectively, where again the edge weights are between 1 and τ. For dense graphs we give lower bounds on the quantum query complexity of Ω(n^{3/2}) for τ > 1 and Ω(τ n) for any 1 ≤ τ ≤ n. Our query algorithm uses a quantum algorithm for graph sparsification by Apers and de Wolf (FOCS 2020) and results on the structure of near-minimum cuts by Kawarabayashi and Thorup (STOC 2015) and Rubinstein, Schramm and Weinberg (ITCS 2018). Our time efficient implementation builds on Karger’s tree packing technique (STOC 1996).
Cite as

Simon Apers and Troy Lee. Quantum Complexity of Minimum Cut. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 28:1-28:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.CCC.2021.28,
  author =	{Apers, Simon and Lee, Troy},
  title =	{{Quantum Complexity of Minimum Cut}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{28:1--28:33},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.28},
  URN =		{urn:nbn:de:0030-drops-143026},
  doi =		{10.4230/LIPIcs.CCC.2021.28},
  annote =	{Keywords: Quantum algorithms, quantum query complexity, minimum cut}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.6
A Unified Framework of Quantum Walk Search

Authors: Simon Apers, András Gilyén, and Stacey Jeffery

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
Many quantum algorithms critically rely on quantum walk search, or the use of quantum walks to speed up search problems on graphs. However, the main results on quantum walk search are scattered over different, incomparable frameworks, such as the hitting time framework, the MNRS framework, and the electric network framework. As a consequence, a number of pieces are currently missing. For example, recent work by Ambainis et al. (STOC'20) shows how quantum walks starting from the stationary distribution can always find elements quadratically faster. In contrast, the electric network framework allows quantum walks to start from an arbitrary initial state, but it only detects marked elements. We present a new quantum walk search framework that unifies and strengthens these frameworks, leading to a number of new results. For example, the new framework effectively finds marked elements in the electric network setting. The new framework also allows to interpolate between the hitting time framework, minimizing the number of walk steps, and the MNRS framework, minimizing the number of times elements are checked for being marked. This allows for a more natural tradeoff between resources. In addition to quantum walks and phase estimation, our new algorithm makes use of quantum fast-forwarding, similar to the recent results by Ambainis et al. This perspective also enables us to derive more general complexity bounds on the quantum walk algorithms, e.g., based on Monte Carlo type bounds of the corresponding classical walk. As a final result, we show how in certain cases we can avoid the use of phase estimation and quantum fast-forwarding, answering an open question of Ambainis et al.
Cite as

Simon Apers, András Gilyén, and Stacey Jeffery. A Unified Framework of Quantum Walk Search. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.STACS.2021.6,
  author =	{Apers, Simon and Gily\'{e}n, Andr\'{a}s and Jeffery, Stacey},
  title =	{{A Unified Framework of Quantum Walk Search}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.6},
  URN =		{urn:nbn:de:0030-drops-136511},
  doi =		{10.4230/LIPIcs.STACS.2021.6},
  annote =	{Keywords: Quantum Algorithms, Quantum Walks, Graph Theory}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.49
Robust Quantum Entanglement at (Nearly) Room Temperature

Authors: Lior Eldar

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We formulate an average-case analog of the NLTS conjecture of Freedman and Hastings (QIC 2014) by asking whether there exist topologically ordered systems with corresponding local Hamiltonians for which the thermal Gibbs state for constant temperature cannot even be approximated by shallow quantum circuits. We then prove this conjecture for nearly optimal parameters: we construct a quantum error correcting code whose corresponding (log) local Hamiltonian has the following property: for nearly constant temperature (temperature decays as 1/log²log(n)) the thermal Gibbs state of that Hamiltonian cannot be approximated by any circuit of depth less than log(n), and it is highly entangled in a well-defined way. This implies that appropriately chosen local Hamiltonians can give rise to ground-state long-range entanglement which can survive without active error correction at temperatures which are nearly independent of the system size: thereby improving exponentially upon previously known bounds.
Cite as

Lior Eldar. Robust Quantum Entanglement at (Nearly) Room Temperature. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 49:1-49:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{eldar:LIPIcs.ITCS.2021.49,
  author =	{Eldar, Lior},
  title =	{{Robust Quantum Entanglement at (Nearly) Room Temperature}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{49:1--49:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.49},
  URN =		{urn:nbn:de:0030-drops-135886},
  doi =		{10.4230/LIPIcs.ITCS.2021.49},
  annote =	{Keywords: Quantum error-correcting codes, Quantum Entanglement, Quantum Locally-Testable Codes, Local Hamiltonians, quantum PCP, NLTS}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.9
Quantum Walk Sampling by Growing Seed Sets

Authors: Simon Apers

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
This work describes a new algorithm for creating a superposition over the edge set of a graph, encoding a quantum sample of the random walk stationary distribution. The algorithm requires a number of quantum walk steps scaling as O~(m^(1/3) delta^(-1/3)), with m the number of edges and delta the random walk spectral gap. This improves on existing strategies by initially growing a classical seed set in the graph, from which a quantum walk is then run. The algorithm leads to a number of improvements: (i) it provides a new bound on the setup cost of quantum walk search algorithms, (ii) it yields a new algorithm for st-connectivity, and (iii) it allows to create a superposition over the isomorphisms of an n-node graph in time O~(2^(n/3)), surpassing the Omega(2^(n/2)) barrier set by index erasure.
Cite as

Simon Apers. Quantum Walk Sampling by Growing Seed Sets. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{apers:LIPIcs.ESA.2019.9,
  author =	{Apers, Simon},
  title =	{{Quantum Walk Sampling by Growing Seed Sets}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.9},
  URN =		{urn:nbn:de:0030-drops-111300},
  doi =		{10.4230/LIPIcs.ESA.2019.9},
  annote =	{Keywords: Quantum algorithms, Quantum walks, Connectivity, Graph theory}
}
  • Refine by Type
  • 15 Document/PDF
  • 8 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 7 2025
  • 1 2024
  • 1 2023
  • 1 2022
  • Show More...

  • Refine by Author
  • 10 Apers, Simon
  • 3 Jeffery, Stacey
  • 2 Gao, Minbo
  • 2 Ji, Zhengfeng
  • 2 Lee, Troy
  • Show More...

  • Refine by Series/Journal
  • 15 LIPIcs

  • Refine by Classification
  • 6 Theory of computation → Graph algorithms analysis
  • 4 Theory of computation → Design and analysis of algorithms
  • 4 Theory of computation → Quantum complexity theory
  • 4 Theory of computation → Quantum computation theory
  • 4 Theory of computation → Quantum query complexity
  • Show More...

  • Refine by Keyword
  • 3 Quantum Algorithms
  • 2 Graph theory
  • 2 Quantum Computing
  • 2 Quantum Walks
  • 2 Quantum algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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