Yasuhiro Takahashi
Yasuhiro Takahashi, Ph.D.
Senior Research Scientist
Computing Theory Research Group
Media Information Laboratory
NTT Communication Science Laboratories
31 MorinosatoWakamiya, Atsugi, Kanagawa 2430198, Japan
Email: yasuhiro.takahashi.rb (at) hco.ntt.co.jp
Japanese version
Research Interests

Quantum Computing, Computational Complexity Theory, Cryptography
List of Publications

Journal Papers
 Yasuhiro Takahashi, Yuki Takeuchi, Seiichiro Tani. Classically simulating quantum circuits with local depolarizing noise, Theoretical Computer Science, Vol. 893, pp. 117132, 2021.
 Yuki Takeuchi, Yasuhiro Takahashi, Seiichiro Tani. Hardness of efficiently generating ground states in postselected quantum computation. Physical Review Research 3, 013213, 2021.
 Yasuhiro Takahashi and Seiichiro Tani. Power of uninitialized qubits in shallow quantum circuits. Theoretical Computer Science, Vol. 851, pp. 129153, 2021.
 Yuki Takeuchi and Yasuhiro Takahashi. Ancilladriven instantaneous quantum polynomial time circuit for quantum supremacy. Physical Review A 94, 062336, 2016.
 Yasuhiro Takahashi and Seiichiro Tani. Collapse of the hierarchy of constantdepth exact quantum circuits. Computational Complexity, Vol. 25 Issue 4, pp. 849881, 2016.
 Yasuhiro Takahashi, Seiichiro Tani, Takeshi Yamazaki, Kazuyuki Tanaka. Commuting quantum circuits with few outputs are unlikely to be classically simulatable. Quantum Information and Computation, Vol. 16 No. 3&4, pp. 251270, 2016.
 Yasuhiro Takahashi, Takeshi Yamazaki, Kazuyuki Tanaka. Hardness of classically simulating quantum circuits with unbounded Toffoli and fanout gates. Quantum Information and Computation, Vol. 14 No. 13&14, pp. 11491164, 2014.
 Yasuhiro Takahashi. An approximately universal set consisting of two observables. International Journal of Quantum Information, Vol. 9 No. 6, pp. 13931412, 2011.
 Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro. Quantum addition circuits and unbounded fanout. Quantum Information and Computation, Vol. 10 No. 9&10, pp. 872890, 2010.
 Yasuhiro Takahashi. Simple sets of measurements for universal quantum computation and graph state preparation. International Journal of Quantum Information, Vol. 8 No. 6, pp. 10011012, 2010.
 Yasuhiro Takahashi. Quantum arithmetic circuits: a survey. IEICE Trans. Fundamentals, Vol. E92A No. 5, pp. 12761283, 2009. (Invited Paper)
 Yasuhiro Takahashi and Noboru Kunihiro. A fast quantum circuit for addition with few qubits. Quantum Information and Computation, Vol. 8 No. 6&7, pp. 636649, 2008.
 Yasuhiro Takahashi, Noboru Kunihiro, Kazuo Ohta. The quantum Fourier transform on a linear nearest neighbor architecture. Quantum Information and Computation, Vol. 7 No. 4, pp. 383391, 2007.
 Yasuhiro Takahashi and Noboru Kunihiro. A quantum circuit for Shor's factoring algorithm using 2n+2 qubits. Quantum Information and Computation, Vol. 6 No. 2, pp. 184192, 2006.
 Yasuhiro Takahashi and Noboru Kunihiro. A linearsize quantum circuit for addition with no ancillary qubits. Quantum Information and Computation, Vol. 5 No. 6, pp. 440448, 2005.
Conference Papers
 Yuki Takeuchi, Yasuhiro Takahashi, Seiichiro Tani. Hardness of efficiently generating ground states in postselected quantum computation. The 21st Asian Quantum Information Science Conference (AQIS 2021), 2021.
 Yuki Takeuchi, Yasuhiro Takahashi, Seiichiro Tani. Efficiently generating ground states is hard for postselected quantum computation. The 16th Conference on Theory of Quantum Computation, Communication, and Cryptography (TQC 2021), 2021.
 Yasuhiro Takahashi, Yuki Takeuchi, Seiichiro Tani. Classically simulating quantum circuits with local depolarizing noise. The 24th Annual Conference on Quantum Information Processing 2021 (QIP 2021), 2021.
 Yasuhiro Takahashi, Yuki Takeuchi, Seiichiro Tani. Classically simulating quantum circuits with local depolarizing noise. The 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), Leibniz International Proceedings in Informatics (LIPIcs) 170, pp. 83:183:13, 2020.
 Yasuhiro Takahashi and Seiichiro Tani. Power of uninitialized qubits in shallow quantum circuits. The 22nd Annual Conference on Quantum Information Processing 2019 (QIP 2019), 2019.
 Yasuhiro Takahashi and Seiichiro Tani. Power of uninitialized qubits in shallow quantum circuits. The 18th Asian Quantum Information Science Conference (AQIS 2018), p. 49, 2018.
 Yasuhiro Takahashi and Seiichiro Tani. Power of uninitialized qubits in shallow quantum circuits. The 35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018), Leibniz International Proceedings in Informatics (LIPIcs) 96, pp. 57:157:13, 2018.
 Yasuhiro Takahashi. On the computational power of constantdepth exact quantum circuits. Computability Theory and Foundations of Mathematics (CTFM 2015), 2015.
 Yasuhiro Takahashi. On the computational power of constantdepth exact quantum circuits. Minisymposium "Quantum Computation and Quantum Information", the 8th International Congress on Industrial and Applied Mathematics (ICIAM 2015), 2015. (Invited Talk)
 Yasuhiro Takahashi, Seiichiro Tani, Takeshi Yamazaki, Kazuyuki Tanaka. Commuting quantum circuits with few outputs are unlikely to be classically simulatable. The 21st International Computing and Combinatorics Conference (COCOON 2015), LNCS 9198, pp. 223234, 2015.
 Yasuhiro Takahashi. On the computational power of constantdepth exact quantum circuits. ELC Workshop at the University of Tokyo on Quantum Complexity Theory (Satellite workshop of AQIS 2014), 2014. (Invited Talk)
 Yasuhiro Takahashi, Takeshi Yamazaki, Kazuyuki Tanaka. Hardness of classically simulating quantum circuits with unbounded Toffoli and fanout gates. The 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013), LNCS 8087, pp. 801812, 2013.
 Yasuhiro Takahashi and Seiichiro Tani. Collapse of the hierarchy of constantdepth exact quantum circuits. The 28th IEEE Conference on Computational Complexity (CCC 2013), pp. 168178, 2013.
 Yasuhiro Takahashi. An approximately universal set consisting of two observables. The 6th Conference on Theory of Quantum Computation, Communication, and Cryptography (TQC 2011), 2011.
 Yasuhiro Takahashi. Reducing the resources of measurementonly quantum computation. The 14th Workshop on Quantum Information Processing 2011 (QIP 2011), 2011.
 Yasuhiro Takahashi. Simple sets of measurements for universal quantum computation and graph state preparation. The 5th Conference on Theory of Quantum Computation, Communication, and Cryptography (TQC 2010), 2010. LNCS 6519, pp. 2634, 2011.
 Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro. Quantum addition circuits and unbounded fanout. The 13th Workshop on Quantum Information Processing 2010 (QIP 2010), 2010.
 Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro. Quantum addition circuits and unbounded fanout. Asian Conference on Quantum Information Science 2009 (AQIS'09), pp. 4546, 2009.
 Yasuhiro Takahashi and Noboru Kunihiro. Circuit for Shor's factoring algorithm with at most 2n+2 qubits. The 4th Workshop on Theory of Quantum Computation, Communication, and Cryptography (TQC 2009), 2009.
 Yasuhiro Takahashi and Noboru Kunihiro. Addition on a linear nearest neighbor architecture. Asian Conference on Quantum Information Science 2008 (AQIS'08), pp. 139140, 2008.
 Yasuhiro Takahashi and Noboru Kunihiro. A fast quantum circuit for addition with few qubits. The 3rd Workshop on Theory of Quantum Computation, Communication, and Cryptography (TQC 2008), pp. 3536, 2008.
 Yasuhiro Takahashi and Noboru Kunihiro. A fast quantum circuit for addition with few qubits. The 11th Workshop on Quantum Information Processing 2008 (QIP 2008), 2007.
 Yasuhiro Takahashi, Noboru Kunihiro, Kazuo Ohta. The quantum Fourier transform on a linear nearest neighbor architecture. Asian Conference on Quantum Information Science 2007 (AQIS'07), pp. 1011, 2007.
 Yasuhiro Takahashi, Noboru Kunihiro, Kazuo Ohta. The quantum Fourier transform on a linear nearest neighbor architecture. The 10th Workshop on Quantum Information Processing 2007 (QIP 2007), 2007.
 Yasuhiro Takahashi, Noboru Kunihiro, Kazuo Ohta. An efficient quantum circuit for addition in GF(p) and Shor's algorithm. Asian Conference on Quantum Information Science 2006 (AQIS'06), pp. 109110, 2006.
 Yasuhiro Takahashi and Noboru Kunihiro. A quantum circuit for Shor's factoring algorithm using 2n+2 qubits. Workshop on Theory of Quantum Computation, Communication, and Cryptography (TQC 2006), pp. 45, 2006.
 Yasuhiro Takahashi and Noboru Kunihiro. A linearsize quantum circuit for addition with no ancillary qubits. ERATO Conference on Quantum Information Science 2005 (EQIS'05), pp. 113114, 2005.
 Noboru Kunihiro, Hirokazu Suzuki, Yasuhiro Takahashi. Shor's factoring algorithm with approximate modular addition. The 8th Workshop on Quantum Information Processing 2005 (QIP 2005), 2005.
 Yasuhiro Takahashi. Some examples of oneway permutations for constantdepth quantum circuits. ERATO Conference on Quantum Information Science 2004 (EQIS'04), pp. 177178, 2004.
 Yasuhiro Takahashi, Seiichiro Tani, Yasuhito Kawano. An explicit construction of oneway permutations for constantdepth quantum circuits. International Symposium on Mesoscopic Superconductivity and Spintronics 2004 (MS+S 2004), 2004.
 Noboru Kunihiro, Yasuhiro Takahashi, Yasuhito Kawano. Reversibility of modular squaring. International Symposium on Mesoscopic Superconductivity and Spintronics 2004 (MS+S2004), 2004.
 Yasuhito Kawano, Seiichiro Tani, Yasuhiro Takahashi, Mayumi Oto, Noboru Kunihiro. NPcompleteness of the initial arrangement of qubits. International Symposium on Mesoscopic Superconductivity and Spintronics 2004 (MS+S 2004), 2004.
 Yasuhiro Takahashi, Yasuhito Kawano, Masahiro Kitagawa. On the computational power of constantdepth quantum circuits with gates for addition. IEEE Congress on Evolutionary Computation 2003 (CEC 2003), Vol. 1, pp. 154161, 2003.
 Yasuhiro Takahashi, Yasuhito Kawano, Masahiro Kitagawa. Constantdepth quantum circuits with gates for addition. ERATO Conference on Quantum Information Science 2003 (EQIS'03), pp. 127128, 2003.
 Yasuhito Kawano, Yasuhiro Takahashi, Shigeru Yamashita, Masahiro Kitagawa. Explicit implementation of quantum computers on a unidirectional periodic structure. Carrier Interactions and Spintronics in Nanostructures (CISN 2003), 2003.
Domestic Workshops
 Yasuhiro Takahashi, Yuki Takeuchi, Seiichiro Tani. Classically simulating quantum circuits with local depolarizing noise. IPSJ SIG on Quantum Software (3rd meeting), 2021.
 Yuki Takeuchi, Yasuhiro Takahashi, Seiichiro Tani. Hardness of efficiently generating ground states in postselected quantum computation. IPSJ SIG on Quantum Software (3rd meeting), 2021.
 Yasuhiro Takahashi, Yuki Takeuchi, Seiichiro Tani. Classically simulating quantum circuits with local depolarizing noise. Theoretical Foundations of Computing (COMP), COMP202033, pp. 2629, 2021.
 Yasuhiro Takahashi, Yuki Takeuchi, Seiichiro Tani. Classically simulating quantum circuits with local depolarizing noise. The 43rd Quantum Information Technology Symposium (QIT43), pp. 5356, 2020.
 Yasuhiro Takahashi and Seiichiro Tani. Power of uninitialized qubits in shallow quantum circuits. The 38th Quantum Information Technology Symposium (QIT38), pp. 1318, 2018.
 Yuki Takeuchi and Yasuhiro Takahashi. Ancilladriven instantaneous quantum polynomial time circuit for quantum supremacy. The 38th Quantum Information Technology Symposium (QIT38), pp. 812, 2018.
 Yasuhiro Takahashi and Seiichiro Tani. Power of uninitialized qubits in shallow quantum circuits. Theoretical Foundations of Computing (COMP), COMP20182, pp. 2326, 2018.
 Yasuhiro Takahashi. Quantum addition circuits and unbounded fanout. CryptoMathCREST MiniWorkshop "Quantum and Cryptography", 2018. (Invited Talk)
 Yuki Takeuchi and Yasuhiro Takahashi. Ancilladriven instantaneous quantum polynomial time circuit for quantum supremacy. The Physical Society of Japan 72nd Annual Meeting, 2017.
 Yasuhiro Takahashi, Takeshi Yamazaki, Kazuyuki Tanaka. Hardness of classically simulating quantum circuits with unbounded Toffoli and fanout gates. Theoretical Foundations of Computing (COMP), COMP201329, pp. 2734, 2013. (Invited Talk)
 Yasuhiro Takahashi. On the computational power of smalldepth quantum circuits. The 28th Quantum Information Technology Symposium (QIT28), 2013. (Invited Talk)
 Eri Koseki, Noboru Kunihiro, Yasuhiro Takahashi. An efficient quantum circuit for orderfinding on a linear nearest neighbor architecture. Symposium on Cryptography and Information Security (SCIS 2008), 2008.
 Eri Koseki, Noboru Kunihiro, Yasuhiro Takahashi, Kazuo Ohta. Resource evaluations of quantum circuits for orderfinding using 2n+O(1) qubits. The 16th Quantum Information Technology Symposium (QIT16), pp. 112117, 2007.
 Eri Koseki, Noboru Kunihiro, Yasuhiro Takahashi, Kazuo Ohta. Strict evaluations of quantum circuits for orderfinding using 2n+\alpha qubits. Symposium on Cryptography and Information Security (SCIS 2007), 2007.
 Yasuhiro Takahashi. Introduction to quantum computation : quantum circuit model. Quantum Information and Computing Seminar in Sendai 2, 2004.
 Yasuhiro Takahashi, Yasuhito Kawano, Masahiro Kitagawa. Elementary arithmetic operations in constantdepth quantum circuits. The Eighth Quantum Information Technology Symposium (QIT8), pp. 195198, 2003.
Society Membership

 The Institute of Electronics, Information and Communication Engineers (IEICE)
 Information Processing Society of Japan (IPSJ)
Committee

 Conference on Reversible Computation (RC 2022), program committee, 2021.
 Conference on Reversible Computation (RC 2017), program committee, 2017.
 The 33rd Quantum Information Technology Symposium (QIT33), organizing committee, 2015.
 Conference on Reversible Computation (RC 2014), program committee, 2014.
 Conference on Theory of Quantum Computation, Communication, and Cryptography (TQC 2012), program committee, 2012.
 Workshop on Theory of Quantum Computation, Communication, and Cryptography (TQC 2008), organizing committee, 2008.
 Workshop on Theory of Quantum Computation, Communication, and Cryptography (TQC 2007), organizing committee, 2007.
 Workshop on Theory of Quantum Computation, Communication, and Cryptography (TQC 2006), organizing committee, 2006.
Award

Biography

 Mar. 2008: Ph.D. in Engineering from the University of ElectroCommunications.
Ph.D. Thesis: Efficient quantum circuits for arithmetic operations and their applications (Supervisor: Prof.
Noboru Kunihiro)
 Apr. 2000: Joined in NTT Communication Science Laboratories.
 Mar. 2000: M.S. in Mathematics from Tohoku University.
Master Thesis: Second order arithmetic and theory of ordinal numbers (Supervisor: Prof. Kazuyuki Tanaka)
 Mar. 1998: B.S. in Mathematics from Tohoku University.
 May 1975: Born in Iwate, Japan.
Last modified: Dec. 2, 2021