9 Search Results for "Chia, Nai-Hui"

Document
DOI: 10.4230/LIPIcs.CCC.2023.33
On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation

Authors: Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, and Yu-Ching Shen

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
Hamiltonian simulation is one of the most important problems in the field of quantum computing. There have been extended efforts on designing algorithms for faster simulation, and the evolution time T for the simulation greatly affect algorithm runtime as expected. While there are some specific types of Hamiltonians that can be fast-forwarded, i.e., simulated within time o(T), for some large classes of Hamiltonians (e.g., all local/sparse Hamiltonians), existing simulation algorithms require running time at least linear in the evolution time T. On the other hand, while there exist lower bounds of Ω(T) circuit size for some large classes of Hamiltonian, these lower bounds do not rule out the possibilities of Hamiltonian simulation with large but "low-depth" circuits by running things in parallel. As a result, physical systems with system size scaling with T can potentially do a fast-forwarding simulation. Therefore, it is intriguing whether we can achieve fast Hamiltonian simulation with the power of parallelism. In this work, we give a negative result for the above open problem in various settings. In the oracle model, we prove that there are time-independent sparse Hamiltonians that cannot be simulated via an oracle circuit of depth o(T). In the plain model, relying on the random oracle heuristic, we show that there exist time-independent local Hamiltonians and time-dependent geometrically local Hamiltonians on n qubits that cannot be simulated via an oracle circuit of depth o(T/n^c), where the Hamiltonians act on n qubits, and c is a constant. Lastly, we generalize the above results and show that any simulators that are geometrically local Hamiltonians cannot do the simulation much faster than parallel quantum algorithms.
Cite as

Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, and Yu-Ching Shen. On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 33:1-33:45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chia_et_al:LIPIcs.CCC.2023.33,
  author =	{Chia, Nai-Hui and Chung, Kai-Min and Hsieh, Yao-Ching and Lin, Han-Hsuan and Lin, Yao-Ting and Shen, Yu-Ching},
  title =	{{On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{33:1--33:45},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.33},
  URN =		{urn:nbn:de:0030-drops-183038},
  doi =		{10.4230/LIPIcs.CCC.2023.33},
  annote =	{Keywords: Hamiltonian simulation, Depth lower bound, Parallel query lower bound}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.64
Parallel Self-Testing of EPR Pairs Under Computational Assumptions

Authors: Honghao Fu, Daochen Wang, and Qi Zhao

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

Abstract
Self-testing is a fundamental feature of quantum mechanics that allows a classical verifier to force untrusted quantum devices to prepare certain states and perform certain measurements on them. The standard approach assumes at least two spatially separated devices. Recently, Metger and Vidick [Metger and Vidick, 2021] showed that a single EPR pair of a single quantum device can be self-tested under computational assumptions. In this work, we generalize their results to give the first parallel self-test of N EPR pairs and measurements on them in the single-device setting under the same computational assumptions. We show that our protocol can be passed with probability negligibly close to 1 by an honest quantum device using poly(N) resources. Moreover, we show that any quantum device that fails our protocol with probability at most ε must be poly(N,ε)-close to being honest in the appropriate sense. In particular, our protocol can test any distribution over tensor products of computational or Hadamard basis measurements, making it suitable for applications such as device-independent quantum key distribution [Metger et al., 2021] under computational assumptions. Moreover, a simplified version of our protocol is the first that can efficiently certify an arbitrary number of qubits of a single cloud quantum computer using only classical communication.
Cite as

Honghao Fu, Daochen Wang, and Qi Zhao. Parallel Self-Testing of EPR Pairs Under Computational Assumptions. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 64:1-64:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fu_et_al:LIPIcs.ICALP.2023.64,
  author =	{Fu, Honghao and Wang, Daochen and Zhao, Qi},
  title =	{{Parallel Self-Testing of EPR Pairs Under Computational Assumptions}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{64:1--64:19},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.64},
  URN =		{urn:nbn:de:0030-drops-181160},
  doi =		{10.4230/LIPIcs.ICALP.2023.64},
  annote =	{Keywords: Quantum complexity theory, self-testing, LWE}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.6
An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes

Authors: Atsuya Hasegawa and François Le Gall

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Recently, Chia, Chung and Lai (STOC 2020) and Coudron and Menda (STOC 2020) have shown that there exists an oracle 𝒪 such that BQP^𝒪 ≠ (BPP^BQNC)^𝒪 ∪ (BQNC^BPP)^𝒪. In fact, Chia et al. proved a stronger statement: for any depth parameter d, there exists an oracle that separates quantum depth d and 2d+1, when polynomial-time classical computation is allowed. This implies that relative to an oracle, doubling quantum depth gives classical and quantum hybrid schemes more computational power. In this paper, we show that for any depth parameter d, there exists an oracle that separates quantum depth d and d+1, when polynomial-time classical computation is allowed. This gives an optimal oracle separation of classical and quantum hybrid schemes. To prove our result, we consider d-Bijective Shuffling Simon’s Problem (which is a variant of d-Shuffling Simon’s Problem considered by Chia et al.) and an oracle inspired by an "in-place" permutation oracle.
Cite as

Atsuya Hasegawa and François Le Gall. An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hasegawa_et_al:LIPIcs.ISAAC.2022.6,
  author =	{Hasegawa, Atsuya and Le Gall, Fran\c{c}ois},
  title =	{{An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.6},
  URN =		{urn:nbn:de:0030-drops-172918},
  doi =		{10.4230/LIPIcs.ISAAC.2022.6},
  annote =	{Keywords: small-depth quantum circuit, hybrid quantum computer, oracle separation}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.47
Quantum Meets the Minimum Circuit Size Problem

Authors: Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, and Ruizhe Zhang

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
In this work, we initiate the study of the Minimum Circuit Size Problem (MCSP) in the quantum setting. MCSP is a problem to compute the circuit complexity of Boolean functions. It is a fascinating problem in complexity theory - its hardness is mysterious, and a better understanding of its hardness can have surprising implications to many fields in computer science. We first define and investigate the basic complexity-theoretic properties of minimum quantum circuit size problems for three natural objects: Boolean functions, unitaries, and quantum states. We show that these problems are not trivially in NP but in QCMA (or have QCMA protocols). Next, we explore the relations between the three quantum MCSPs and their variants. We discover that some reductions that are not known for classical MCSP exist for quantum MCSPs for unitaries and states, e.g., search-to-decision reductions and self-reductions. Finally, we systematically generalize results known for classical MCSP to the quantum setting (including quantum cryptography, quantum learning theory, quantum circuit lower bounds, and quantum fine-grained complexity) and also find new connections to tomography and quantum gravity. Due to the fundamental differences between classical and quantum circuits, most of our results require extra care and reveal properties and phenomena unique to the quantum setting. Our findings could be of interest for future studies, and we post several open problems for further exploration along this direction.
Cite as

Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, and Ruizhe Zhang. Quantum Meets the Minimum Circuit Size Problem. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chia_et_al:LIPIcs.ITCS.2022.47,
  author =	{Chia, Nai-Hui and Chou, Chi-Ning and Zhang, Jiayu and Zhang, Ruizhe},
  title =	{{Quantum Meets the Minimum Circuit Size Problem}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{47:1--47:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.47},
  URN =		{urn:nbn:de:0030-drops-156433},
  doi =		{10.4230/LIPIcs.ITCS.2022.47},
  annote =	{Keywords: Quantum Computation, Quantum Complexity, Minimum Circuit Size Problem}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.47
Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension

Authors: Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, and Chunhao Wang

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/LIPIcs.MFCS.2020.23
Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming

Authors: Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/LIPIcs.CCC.2020.16
On the Quantum Complexity of Closest Pair and Related Problems

Authors: Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, and Ruizhe Zhang

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

Abstract
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.
Cite as

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-dev.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
DOI: 10.4230/LIPIcs.ITC.2020.8
Lower Bounds for Function Inversion with Quantum Advice

Authors: Kai-Min Chung, Tai-Ning Liao, and Luowen Qian

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Function inversion is the problem that given a random function f: [M] → [N], we want to find pre-image of any image f^{-1}(y) in time T. In this work, we revisit this problem under the preprocessing model where we can compute some auxiliary information or advice of size S that only depends on f but not on y. It is a well-studied problem in the classical settings, however, it is not clear how quantum algorithms can solve this task any better besides invoking Grover’s algorithm [Grover, 1996], which does not leverage the power of preprocessing. Nayebi et al. [Nayebi et al., 2015] proved a lower bound ST² ≥ ̃Ω(N) for quantum algorithms inverting permutations, however, they only consider algorithms with classical advice. Hhan et al. [Minki Hhan et al., 2019] subsequently extended this lower bound to fully quantum algorithms for inverting permutations. In this work, we give the same asymptotic lower bound to fully quantum algorithms for inverting functions for fully quantum algorithms under the regime where M = O(N). In order to prove these bounds, we generalize the notion of quantum random access code, originally introduced by Ambainis et al. [Ambainis et al., 1999], to the setting where we are given a list of (not necessarily independent) random variables, and we wish to compress them into a variable-length encoding such that we can retrieve a random element just using the encoding with high probability. As our main technical contribution, we give a nearly tight lower bound (for a wide parameter range) for this generalized notion of quantum random access codes, which may be of independent interest.
Cite as

Kai-Min Chung, Tai-Ning Liao, and Luowen Qian. Lower Bounds for Function Inversion with Quantum Advice. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.ITC.2020.8,
  author =	{Chung, Kai-Min and Liao, Tai-Ning and Qian, Luowen},
  title =	{{Lower Bounds for Function Inversion with Quantum Advice}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.8},
  URN =		{urn:nbn:de:0030-drops-121134},
  doi =		{10.4230/LIPIcs.ITC.2020.8},
  annote =	{Keywords: Cryptanalysis, Data Structures, Quantum Query Complexity}
}
Document
DOI: 10.4230/LIPIcs.TQC.2016.6
How Hard Is Deciding Trivial Versus Nontrivial in the Dihedral Coset Problem?

Authors: Nai-Hui Chia and Sean Hallgren

Published in: LIPIcs, Volume 61, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)

Abstract
We study the hardness of the dihedral hidden subgroup problem. It is known that lattice problems reduce to it, and that it reduces to random subset sum with density > 1 and also to quantum sampling subset sum solutions. We examine a decision version of the problem where the question asks whether the hidden subgroup is trivial or order two. The decision problem essentially asks if a given vector is in the span of all coset states. We approach this by first computing an explicit basis for the coset space and the perpendicular space. We then look at the consequences of having efficient unitaries that use this basis. We show that if a unitary maps the basis to the standard basis in any way, then that unitary can be used to solve random subset sum with constant density >1. We also show that if a unitary can exactly decide membership in the coset subspace, then the collision problem for subset sum can be solved for density >1 but approaching 1 as the problem size increases. This strengthens the previous hardness result that implementing the optimal POVM in a specific way is as hard as quantum sampling subset sum solutions.
Cite as

Nai-Hui Chia and Sean Hallgren. How Hard Is Deciding Trivial Versus Nontrivial in the Dihedral Coset Problem?. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chia_et_al:LIPIcs.TQC.2016.6,
  author =	{Chia, Nai-Hui and Hallgren, Sean},
  title =	{{How Hard Is Deciding Trivial Versus Nontrivial in the Dihedral Coset Problem?}},
  booktitle =	{11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-019-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{61},
  editor =	{Broadbent, Anne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.6},
  URN =		{urn:nbn:de:0030-drops-66877},
  doi =		{10.4230/LIPIcs.TQC.2016.6},
  annote =	{Keywords: Quantum algorithms, hidden subgroup problem, random subset sum problem}
}
  • Refine by Author
  • 6 Chia, Nai-Hui
  • 4 Lin, Han-Hsuan
  • 3 Wang, Chunhao
  • 2 Chung, Kai-Min
  • 2 Zhang, Ruizhe
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Quantum complexity theory
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Cryptographic primitives
  • 1 Theory of computation → Interactive proof systems
  • 1 Theory of computation → Oracles and decision trees
  • Show More...

  • Refine by Keyword
  • 1 Closest pair
  • 1 Cryptanalysis
  • 1 Data Structures
  • 1 Depth lower bound
  • 1 Fine grained complexity
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 4 2020
  • 2 2022
  • 2 2023
  • 1 2016

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 Imprint Privacy Contact