Zobrazeno 1 - 10
of 67
pro vyhledávání: '"Tamaki, Suguru"'
Autor:
Buhrman, Harry, Gharibian, Sevag, Landau, Zeph, Gall, François Le, Schuch, Norbert, Tamaki, Suguru
Estimating ground state energies of many-body Hamiltonians is a central task in many areas of quantum physics. In this work, we give quantum algorithms which, given any $k$-body Hamiltonian $H$, compute an estimate for the ground state energy and pre
Externí odkaz:
http://arxiv.org/abs/2407.03073
Autor:
Morimae, Tomoyuki, Tamaki, Suguru
Publikováno v:
Quantum 4, 329 (2020)
It is known that several sub-universal quantum computing models, such as the IQP model, the Boson sampling model, the one-clean qubit model, and the random circuit model, cannot be classically simulated in polynomial time under certain conjectures in
Externí odkaz:
http://arxiv.org/abs/1912.06336
Autor:
Higashikawa, Yuya, Katoh, Naoki, Lin, Guohui, Miyano, Eiji, Tamaki, Suguru, Teruyama, Junichi, Zhu, Binhai
Throughout this paper, a persistence diagram ${\cal P}$ is composed of a set $P$ of planar points (each corresponding to a topological feature) above the line $Y=X$, as well as the line $Y=X$ itself, i.e., ${\cal P}=P\cup\{(x,y)|y=x\}$. Given a set o
Externí odkaz:
http://arxiv.org/abs/1910.01753
The Max-Cut problem is known to be NP-hard on general graphs, while it can be solved in polynomial time on planar graphs. In this paper, we present a fixed-parameter tractable algorithm for the problem on `almost' planar graphs: Given an $n$-vertex g
Externí odkaz:
http://arxiv.org/abs/1904.05011
Fine-grained quantum supremacy is a study of proving (nearly) tight time lower bounds for classical simulations of quantum computing under "fine-grained complexity" assumptions. We show that under conjectures on Orthogonal Vectors (OV), 3-SUM, All-Pa
Externí odkaz:
http://arxiv.org/abs/1902.08382
Autor:
Morimae, Tomoyuki, Tamaki, Suguru
Publikováno v:
Quantum Information and Computation 19, 1089-1115 (2019)
Output probability distributions of several sub-universal quantum computing models cannot be classically efficiently sampled unless some unlikely consequences occur in classical complexity theory, such as the collapse of the polynomial-time hierarchy
Externí odkaz:
http://arxiv.org/abs/1901.01637
Autor:
Tamaki, Suguru
Kyoto University (京都大学)
0048
甲第12459号
情博第213号
新制||情||46(附属図書館)
UT51-2006-J450
学位規則第4条第1項該当
0048
甲第12459号
情博第213号
新制||情||46(附属図書館)
UT51-2006-J450
学位規則第4条第1項該当
Externí odkaz:
http://hdl.handle.net/2433/68895
We present a (full) derandomization of HSSW algorithm for 3-SAT, proposed by Hofmeister, Sch\"oning, Schuler, and Watanabe in [STACS'02]. Thereby, we obtain an O(1.3303^n)-time deterministic algorithm for 3-SAT, which is currently fastest.
Comme
Comme
Externí odkaz:
http://arxiv.org/abs/1102.3766
Publikováno v:
In Theoretical Computer Science 2011 412(35):4613-4618
Publikováno v:
In Theoretical Computer Science 2010 411(7):1182-1191