From the 1 of 9 linked papers with an AI index.
9 papers
Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry
Shuji Horinaga, Takashi Yamakawa
The paper presents a quantum algorithm that solves the Optimal Polynomial Intersection problem in the worst case for parameter regimes beyond those achievable by decoded quantum in…
Separating Non-Interactive Classical Verification of Quantum Computation from Falsifiable Assumptions
Mohammed Barhoush, Tomoyuki Morimae, Ryo Nishimaki +1
Mahadev [SIAM J. Comput. 2022] introduced the first protocol for classical verification of quantum computation based on the Learning-with-Errors (LWE) assumption, achieving a 4-mes…
Quantum Cryptography and Hardness of Non-Collapsing Measurements
Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa
One-way puzzles (OWPuzzs) introduced by Khurana and Tomer [STOC 2024] are a natural quantum analogue of one-way functions (OWFs), and one of the most fundamental primitives in ''Mi…
CountCrypt: Quantum Cryptography between QCMA and PP
Eli Goldin, Tomoyuki Morimae, Saachi Mutreja +1
We construct a unitary oracle relative to which but quantum-computation-classical-communication (QCCC) commitments and QCCC multiparty non-interactive…
Proofs of quantum memory
Minki Hhan, Tomoyuki Morimae, Yasuaki Okinaka +1
With the rapid advances in quantum computer architectures and the emerging prospect of large-scale quantum memory, it is becoming essential to classically verify that remote device…
From Worst-Case Hardness of to Quantum Cryptography via Quantum Indistinguishability Obfuscation
Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa
Indistinguishability obfuscation (iO) has emerged as a powerful cryptographic primitive with many implications. While classical iO, combined with the infinitely-often worst-case ha…