Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
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)
@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} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
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)
@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} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
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)
@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} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
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)
@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} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
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)
@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} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
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)
@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} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
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)
@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} }
Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)
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)
@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} }
Published in: LIPIcs, Volume 61, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)
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)
@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} }
Feedback for Dagstuhl Publishing