2024/12/07 更新

写真a

タニ セイイチロウ
谷 誠一郎
所属
教育・総合科学学術院 教育学部
職名
教授
学位
博士(情報理工学) ( 東京大学 )
プロフィール

1993年3月 京都大学工学部情報工学科卒業. 1995年3月 東京大学大学院理学系研究科情報科学専攻修了.博士(情報理工学).1995年4月〜2024年3月 日本電信電話株式会社 コミュニケーション科学基礎研究所 特別研究員/理論量子情報研究センタ長(最終職位).2004年4月〜2009年9月 JST ERATO 今井量子計算機構プロジェクト/JST ERATO-SORST 量子情報システムアーキテクチャ 研究員(兼任).2010年2月〜2011年2月 Waterloo 大学 量子計算研究所 客員研究員.2020年10月〜現在 日本学術会議 連携会員. 2022年4月〜2024年3月 東京工業大学 国際先駆研究機構 特定教授. 電子情報通信学会 業績賞・ISS論文賞,前島密賞,SCAT会長賞受賞.電子情報通信学会,情報処理学会,IEEE,ACM各会員.専門は,理論計算機科学,特に,量子アルゴリズム,量子計算量理論,分散計算.

経歴

  • 2024年04月
    -
    継続中

    早稲田大学   教育・総合科学学術院   教授

  • 2020年10月
    -
    継続中

    日本学術会議   連携会員

  • 2023年10月
    -
    2024年03月

    NTT 物性科学基礎研究所   理論量子情報研究センタ   プロジェクトマネージャ

  • 2022年04月
    -
    2024年03月

    東京工業大学   国際先端研究機構 量子コンピューティング研究拠点   特定教授

  • 2016年10月
    -
    2024年03月

    日本電信電話株式会社   主幹研究員〜特別研究員

  • 2016年10月
    -
    2021年03月

    NTT コミュニケーション科学基礎研究所   情報基礎理論研究グループ   グループリーダ

  • 2016年
    -
    2018年

    東京工業大学   非常勤講師

  • 1995年04月
    -
    2016年09月

    日本電信電話株式会社   社員~主任研究員

  • 2010年02月
    -
    2011年02月

    Waterloo大学   量子計算研究所   客員研究員

  • 2005年10月
    -
    2009年09月

    JST   ERATO-SORST 量子情報システムアーキテクチャ   研究員(兼任)

  • 2004年04月
    -
    2005年09月

    JST   ERATO 今井量子計算機構プロジェクト   研究員(兼任)

▼全件表示

委員歴

  • 2018年
    -
    継続中

    文部科学省 「光・量子飛躍フラッグシッププログラム (Q-LEAP)」  アドバイザリーボード

  • 2018年
    -
    継続中

    JST CREST [コンピューティング基盤] 「Society5.0を支える革新的コンピューティング技術」  領域アドバイザ

  • 2012年
    -
    継続中

    AMS Mathematical Reviews,  reviewer

  • 2024年
    -
     

    国際会議 Asian Quantum Information Science Conference (AQIS 2024)  プログラム委員長

  • 2023年
     
     

    国際会議 Asian Quantum Information Science Conference (AQIS 2023)  プログラム委員

  • 2022年04月
    -
    2022年12月

    The International Symposium on Quantum Science, Technology and Innovation (Quantum Innovation 2022)  組織委員

  • 2021年04月
    -
    2021年12月

    The International Symposium on Quantum Science, Technology and Innovation (Quantum Innovation 2021)  組織委員

  • 2015年
    -
    2021年05月

    電子情報通信学会  コンピューテーション研究会 専門委員

  • 2016年
    -
    2021年03月

    JST さきがけ 「量子の状態制御と機能化」  領域アドバイザ

  • 2021年
     
     

    国際会議21th Asian Quantum Information Science Conference (AQIS 2021)  プログラム委員

  • 2018年
     
     

    国際会議 Asian Quantum Information Science Conference (AQIS 2018)  プログラム委員

  • 2012年
    -
    2018年

    情報処理学会  論文誌査読委員

  • 2016年
     
     

    国際会議 Asian Quantum Information Science Conference (AQIS 2016)  プログラム委員

  • 2008年
    -
    2012年

    情報処理学会  論文誌ジャーナル編集委員・論文賞委員

  • 2010年
     
     

    国際会議 Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC 2010)  プログラム委員

  • 2009年
    -
     

    電子情報通信学会  小特集 “Frontier of Quantum Computing” ゲスト編集委員長, IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sceinces, Vol. E92-A, No.5, 2009.

  • 2005年
    -
    2009年

    情報処理学会  アルゴリズム研究運営委員

  • 2005年
    -
     

    情報処理学会論文誌, vol.46, No.10, 2005.  「量子計算と量子情報」特集号 ゲスト編集委員長

  • 2002年
    -
    2004年

    電子情報通信学会  会誌編集委員(WG A)

▼全件表示

所属学協会

  •  
     
     

    ACM

  •  
     
     

    IEEE

  •  
     
     

    情報処理学会

  •  
     
     

    電子情報通信学会

研究分野

  • 情報学基礎論

研究キーワード

  • 分散アルゴリズム

  • 量子コンピューター

  • 量子情報理論

  • 量子情報

  • 量子アルゴリズム

  • 通信プロトコル

  • 量子計算

  • 二分決定グラフ

  • 計算量理論

  • 分散計算

  • アルゴリズム

▼全件表示

受賞

  • SCAT会長賞

    2024年01月   一般財団法人テレコム先端技術研究支援センター   量子計算機アルゴリズムの先駆的研究を通じた耐量子計算機暗号技術の安全性評価への貢献  

    受賞者: 谷 誠一郎

  • 前島密賞

    2023年02月   公益財団法人通信文化協会   量子計算アルゴリズムの先駆的研究と耐量子計算機暗号の安全性評価への貢献  

    受賞者: 谷 誠一郎, 高橋 康博

  • 業績賞

    2019年   電子情報通信学会   量子アルゴリズムに関する先駆的研究  

    受賞者: 谷誠一郎, 高橋康博

  • 平成12年度 情報システムソサイエティ論文賞(先見論文)

    2001年   電子情報通信学会   The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram  

    受賞者: 谷誠一郎, 濱口清治, 矢島脩三

 

論文

  • Probabilistic unitary synthesis with optimal accuracy

    seiseki akibue, Go Kato, Seiichiro Tani

    ACM Transactions on Quantum Computing    2024年05月

     概要を見る

    The purpose of unitary synthesis is to find a gate sequence that optimally approximates a target unitary transformation. A new synthesis approach, called probabilistic synthesis, has been introduced, and its superiority has been demonstrated over traditional deterministic approaches with respect to approximation error and gate length. However, the optimality of current probabilistic synthesis algorithms is unknown. We obtain the tight lower bound on the approximation error obtained by the optimal probabilistic synthesis, which guarantees the sub-optimality of current algorithms. We also show its tight upper bound, which improves and unifies current upper bounds depending on the class of target unitaries. These two bounds reveal the fundamental relationship of approximation error between probabilistic approximation and deterministic approximation of unitary transformations. From a computational point of view, we show that the optimal probability distribution can be computed by the semidefinite program (SDP) we construct. We also construct an efficient probabilistic synthesis algorithm for single-qubit unitaries, rigorously estimate its time complexity, and show that it reduces the approximation error quadratically compared with deterministic algorithms.

    DOI

  • Probabilistic state synthesis based on optimal convex approximation

    Seiseki Akibue, Go Kato, Seiichiro Tani

    npj Quantum Information   10 ( 1 )  2024年01月  [査読有り]

     概要を見る

    When preparing a pure state with a quantum circuit, there is an unavoidable approximation error due to the compilation error in fault-tolerant implementation. A recently proposed approach called probabilistic state synthesis, where the circuit is probabilistically sampled, is able to reduce the approximation error compared to conventional deterministic synthesis. In this paper, we demonstrate that the optimal probabilistic synthesis quadratically reduces the approximation error. Moreover, we show that a deterministic synthesis algorithm can be efficiently converted into a probabilistic one that achieves this quadratic error reduction. We also numerically demonstrate how this conversion reduces the T-count and analytically prove that this conversion halves an information-theoretic lower bound on the circuit size. In order to derive these results, we prove general theorems about the optimal convex approximation of a quantum state. Furthermore, we demonstrate that this theorem can be used to analyze an entanglement measure.

    DOI DOI2

  • Rewindable quantum computation and its equivalence to cloning and adaptive postselection

    Ryo Hiromasa, Akihiro Mizutani, Yuki Takeuchi, Seiichiro Tani

    Leibniz International Proceedings in Informatics, LIPIcs   266  2023年07月  [査読有り]

     概要を見る

    We define rewinding operators that invert quantum measurements. Then, we define complexity classes RwBQP, CBQP, and AdPostBQP as sets of decision problems solvable by polynomial-size quantum circuits with a polynomial number of rewinding operators, cloning operators, and adaptive postselections, respectively. Our main result is that BPPPP⊇ RwBQP = CBQP = AdPostBQP ⊇ PSPACE. As a byproduct of this result, we show that any problem in PostBQP can be solved with only postselections of outputs whose probabilities are polynomially close to one. Under the strongly believed assumption that BQP ⊉ SZK, or the shortest independent vectors problem cannot be efficiently solved with quantum computers, we also show that a single rewinding operator is sufficient to achieve tasks that are intractable for quantum computation. In addition, we consider rewindable Clifford and instantaneous quantum polynomial time circuits.

    DOI DOI2

  • Space-Bounded Unitary Quantum Computation with Postselection.

    Seiichiro Tani

    Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)   241   81:1 - 81:15  2022年08月  [査読有り]  [国際誌]

    担当区分:筆頭著者, 責任著者

    DOI DOI2

  • Sumcheck-based delegation of quantum computing to rational server.

    Yuki Takeuchi, Tomoyuki Morimae, Seiichiro Tani

    Theoretical Computer Science   924   46 - 67  2022年07月  [査読有り]  [国際誌]

    DOI

  • Computational self-testing for entangled magic states

    Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa, Seiichiro Tani

    Physical Review A   106 ( L010601 )  2022年07月  [査読有り]  [国際誌]

    DOI

  • Quadratic improvement on accuracy of approximating pure quantum states and unitary gates by probabilistic implementation

    Seiseki Akibue, Go Kato, Seiichiro Tani

    arXive   quant-ph ( 2111.05531 )  2021年11月

    DOI

  • Classically simulating quantum circuits with local depolarizing noise

    Yasuhiro Takahashi, Yuki Takeuchi, Seiichiro Tani

    THEORETICAL COMPUTER SCIENCE   893   117 - 132  2021年11月  [査読有り]  [国際誌]

     概要を見る

    We study the effect of noise on the classical simulatability of quantum circuits defined by computationally tractable (CT) states and efficiently computable sparse (ECS) operations. Examples of such circuits, which we call CT-ECS circuits, are IQP, Clifford Magic, and conjugated Clifford circuits. This means that there exist various CT-ECS circuits such that their output probability distributions are anti-concentrated and not classically simulatable in the noise-free setting (under plausible assumptions). First, we consider a noise model where a depolarizing channel with an arbitrarily small constant rate is applied to each qubit at the end of computation. We show that, under this noise model, if an approximate value of the noise rate is known, any CT-ECS circuit with an anti-concentrated output probability distribution is classically simulatable. This indicates that the presence of small noise drastically affects the classical simulatability of CT-ECS circuits. Then, we consider an extension of the noise model where the noise rate can vary with each qubit, and provide a similar sufficient condition for classically simulating CT-ECS circuits with anti-concentrated output probability distributions. (c) 2021 The Authors. Published by Elsevier B.V.

    DOI

  • Theoretical Approach to Overcome Difficulties in Implementing Quantum Computers

    Seiseki Akibue, Yuki Takeuchi, Yasuhiro Takahashi, Go Kato, Seiichiro Tani

    NTT Technical Review   19 ( 5 ) 34 - 39  2021年05月

    DOI

  • Hardness of efficiently generating ground states in postselected quantum computation

    Yuki Takeuchi, Yasuhiro Takahashi, Seiichiro Tani

    PHYSICAL REVIEW RESEARCH   3 ( 013213 )  2021年03月  [査読有り]

     概要を見る

    Generating ground states of any local Hamiltonians seems to be impossible in quantum polynomial time. In this paper, we give evidence for the impossibility by applying an argument used in the quantum-computational-supremacy approach. More precisely, we show that if ground states of any 3-local Hamiltonians can be approximately generated in quantum polynomial time with postselection, then PP = PSPACE. Our result is superior to the existing findings in the sense that we reduce the impossibility to an unlikely relation between classical complexity classes. We also discuss what makes efficiently generating the ground states hard for postselected quantum computation.

    DOI

  • Power of uninitialized qubits in shallow quantum circuits

    Yasuhiro Takahashi, Seiichiro Tani

    THEORETICAL COMPUTER SCIENCE   851   129 - 153  2021年01月  [査読有り]

     概要を見る

    We study uninitialized qubits, whose initial state is arbitrary and unknown, in relation to the computational power of shallow quantum circuits. To do this, we consider uniform families of shallow quantum circuits with n input qubits, O (log n) initialized ancillary qubits, and n(O(1)) uninitialized ancillary qubits, where the input qubits only act as control qubits. We show that such a circuit with depth O((log n)(2)) can compute any symmetric Boolean function on n bits that is computable by a uniform family of polynomial-size classical circuits. Since it is unlikely that this can be done with only O(log n) initialized ancillary qubits, our result provides evidence that the presence of uninitialized ancillary qubits increases the computational power of shallow quantum circuits with only O (log n) initialized ancillary qubits. On the other hand, to understand the limitations of uninitialized qubits, we focus on sub-logarithmic-depth quantum circuits and show the impossibility of computing the parity function on n bits. (C) 2020 Elsevier B.V. All rights reserved.

    DOI

  • Quantum algorithm for the multicollision problem

    Akinori Hosoyamada, Yu Sasaki, Seiichiro Tani, Keita Xagawa

    THEORETICAL COMPUTER SCIENCE   842   100 - 117  2020年11月  [査読有り]

     概要を見る

    The current paper presents a new quantum algorithm for finding multicollisions, often denoted by l-collisions, where an l-collision for a function is a set of L distinct inputs that are mapped by the function to the same value. In cryptology, it is important to study how many queries are required to find an l-collision for a random function of which domain is larger than its range. However, the problem of finding l-collisions for random functions has not received much attention in the quantum setting. The tight bound of quantum query complexity for finding a 2-collisions of a random function has been revealed to be Theta(N-1/3), where N is the size of the range of the function, but neither the lower nor upper bounds are known for general l-collisions. The paper first integrates the results from existing research to derive several new observations, e.g., l-collisions can be generated only with O(N-1/2) quantum queries for any integer constant L. It then provides a quantum algorithm that finds an l-collision for a random function with the average quantum query complexity of O(N(2l-1 -1)/(2(l)-1)), which matches the tight bound of Theta(N-1/3) for l = 2 and improves upon the known bounds, including the above simple bound of O(N-1/2). More generally, the algorithm achieves the average quantum query complexity of O(c(N).N(2l-1 -1)/(2l-1)), and runs over (O) over tilde (c(N).N(2l-1 -1)/2l-1)) qubits in a (O) over tilde (c(N).N(2l-1 -1)/2l-1)) expected time for a random function F : X -> Y such that vertical bar X vertical bar >= l . vertical bar Y vertical bar/c(N) for any 1 <= c(N) is an element of o (N1/(2l-1)), where it is assumed that QRAM is available. With the same query complexity, it is actually able to find a multiclaw for random functions, which is harder to find than a multicollision. (C) 2020 Elsevier B.V. All rights reserved.

    DOI

  • Sumcheck-Based Delegation of Quantum Computing to Rational Server

    Yuki Takeuchi, Tomoyuki Morimae, Seiichiro Tani

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   12337   69 - 81  2020年

     概要を見る

    Recently, a new model of delegated quantum computing has been proposed, namely, rational delegated quantum computing. In this model, after a client delegates quantum computing to a server, the client pays a reward to the server. In this paper, we propose novel one-round rational delegated quantum computing protocols. The construction of the previous rational protocols depends on gate sets, while our sumcheck technique can be easily realized with any local gate set. We also show that a constant reward gap can be achieved if two non-communicating but entangled rational servers are allowed. Furthermore, we show, under a certain condition, the equivalence between rational and ordinary delegated quantum computing protocols.

    DOI

  • Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams.

    Seiichiro Tani

    Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), Leibniz International Proceedings in Informatics (LIPIcs),   162   36:1 - 36:19  2020年  [査読有り]

    DOI

  • Classically Simulating Quantum Circuits with Local Depolarizing Noise.

    Yasuhiro Takahashi, Yuki Takeuchi, Seiichiro Tani

    Proc. 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)     83:1 - 83:13  2020年  [査読有り]

    DOI

  • Improved quantum multicollision-finding algorithm

    Akinori Hosoyamada, Yu Sasaki, Seiichiro Tani, Keita Xagawa

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   11505 LNCS   350 - 367  2019年  [査読有り]

     概要を見る

    © Springer Nature Switzerland AG 2019. The current paper improves the number of queries of the previous quantum multi-collision finding algorithms presented by Hosoyamada et al. at Asiacrypt 2017. Let an l-collision be a tuple of l distinct inputs that result in the same output of a target function. In cryptology, it is important to study how many queries are required to find l-collisions for random functions of which domains are larger than ranges. The previous algorithm finds an l-collision for a random function by recursively calling the algorithm for finding (l-l) -collisions, and it achieves the average quantum query complexity of (Formula presented), where N is the range size of target functions. The new algorithm removes the redundancy of the previous recursive algorithm so that different recursive calls can share a part of computations. The new algorithm finds an l-collision for random functions with the average quantum query complexity of (Formula presented), which improves the previous bound for all l ≥3 (the new and previous algorithms achieve the optimal bound for l=2). More generally, the new algorithm achieves the average quantum query complexity of (Formula presented) for a random function (Formula presented) such that (Formula presented) for any (Formula presented). With the same query complexity, it also finds a multiclaw for random functions, which is harder to find than a multicollision.

    DOI

  • Impossibility of blind quantum sampling for classical client.

    Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi, Seiichiro Tani

    Quantum Inf. Comput.   19 ( 9&10 ) 793 - 806  2019年  [査読有り]

     概要を見る

    © Rinton Press. Blind quantum computing enables a client, who can only generate or measure singlequbit states, to delegate quantum computing to a remote quantum server in such a way that the input, output, and program are hidden from the server. It is an open problem whether a completely classical client can delegate quantum computing blindly (in the information theoretic sense). In this paper, we show that if a completely classical client can blindly delegate sampling of subuniversal models, such as the DQC1 model and the IQP model, then the polynomial-time hierarchy collapses to the third level. Our delegation protocol is the one where the client first sends a polynomial-length bit string to the server and then the server returns a single bit to the client. Generalizing the no-go result to more general setups is an open problem.

  • Impossibility of Classically Simulating One-Clean-Qubit Model with Multiplicative Error

    Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, Seiichiro Tani

    Physical Review Letters   120 ( 20 ) 200502 - 200502  2018年05月  [査読有り]

     概要を見る

    The one-clean-qubit model (or the deterministic quantum computation with one quantum bit model) is a restricted model of quantum computing where all but a single input qubits are maximally mixed. It is known that the probability distribution of measurement results on three output qubits of the one-clean-qubit model cannot be classically efficiently sampled within a constant multiplicative error unless the polynomial-time hierarchy collapses to the third level [T. Morimae, K. Fujii, and J. F. Fitzsimons, Phys. Rev. Lett. 112, 130502 (2014)]. It was open whether we can keep the no-go result while reducing the number of output qubits from three to one. Here, we solve the open problem affirmatively. We also show that the third-level collapse of the polynomial-time hierarchy can be strengthened to the second-level one. The strengthening of the collapse level from the third to the second also holds for other subuniversal models such as the instantaneous quantum polynomial model [M. Bremner, R. Jozsa, and D. J. Shepherd, Proc. R. Soc. A 467, 459 (2011)] and the boson sampling model [S. Aaronson and A. Arkhipov, STOC 2011, p. 333]. We additionally study the classical simulatability of the one-clean-qubit model with further restrictions on the circuit depth or the gate types.

    DOI DOI2 PubMed CiNii

  • Power of Uninitialized Qubits in Shallow Quantum Circuits.

    Yasuhiro Takahashi, Seiichiro Tani

    35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France   851   57:1-57:13 - 153  2018年  [査読有り]

    DOI DOI2

  • A FAST EXACT QUANTUM ALGORITHM FOR SOLITUDE VERIFICATION

    Seiichiro Tani

    QUANTUM INFORMATION & COMPUTATION   17 ( 1-2 ) 15 - 40  2017年02月  [査読有り]

     概要を見る

    Solitude verification is arguably one of the simplest fundamental problems in distributed computing, where the goal is to verify that there is a unique contender in a network. This paper devises a quantum algorithm that exactly solves the problem on an anonymous network, which is known as a network model with minimal assumptions [Angluin, STOC' 80]. The algorithm runs in O (N) rounds if every party initially has the common knowledge of an upper bound N on the number of parties. This implies that all solvable problems can be solved in O (N) rounds on average without error (i.e., with zero-sided error) on the network. As a generalization, a quantum algorithm that works in O (N log(2) (max {k,2})) rounds is obtained for the problem of exactly computing any symmetric Boolean function, over n distributed input bits, which is constant over all the n bits whose sum is larger than k for k is an element of{0,1, . . . , N - 1}. All these algorithms work with the bit complexities bounded by a polynomial in N

  • Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits

    Yasuhiro Takahashi, Seiichiro Tani

    COMPUTATIONAL COMPLEXITY   25 ( 4 ) 849 - 881  2016年12月  [査読有り]

     概要を見る

    We study the quantum complexity class of quantum operations implementable exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates. Our main result is that the quantum OR operation is in , which is an affirmative answer to the question posed by Hoyer and palek. In sharp contrast to the strict hierarchy of the classical complexity classes: , our result with Hoyer and palek's one implies the collapse of the hierarchy of the corresponding quantum ones: . Then, we show that there exists a constant-depth subquadratic-size quantum circuit for the quantum threshold operation. This allows us to obtain a better bound on the size difference between the and circuits for implementing the same operation. Lastly, we show that, if the quantum Fourier transform modulo a prime is in , there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a oracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a circuit with gates for the quantum Fourier transform.

    DOI DOI2

  • Quantum Query Complexity of Almost All Functions with Fixed On-set Size

    Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita

    COMPUTATIONAL COMPLEXITY   25 ( 4 ) 723 - 735  2016年12月  [査読有り]

     概要を見る

    This paper considers the quantum query complexity of almost all functions in the set of -variable Boolean functions with on-set size , where the on-set size is the number of inputs on which the function is true. The main result is that, for all functions in except its polynomially small fraction, the quantum query complexity is Theta (logM/c+log N- log log M + root N) for a constant . This is quite different from the quantum query complexity of the hardest function in F-N,F-M : Theta (root N logM/c+log N- log log M + root N) . In contrast, almost all functions in have the same randomized query complexity as the hardest one, up to a constant factor.

    DOI

  • COMMUTING QUANTUM CIRCUITS WITH FEW OUTPUTS ARE UNLIKELY TO BE CLASSICALLY SIMULATABLE

    Yasuhiro Takahashi, Seiichiro Tani, Takeshi Yamazaki, Kazuyuki Tanaka

    QUANTUM INFORMATION & COMPUTATION   16 ( 3-4 ) 251 - 270  2016年03月  [査読有り]

     概要を見る

    We study the classical simulatability of commuting quantum circuits with n input qubits and O(log n) output qubits, where a quantum circuit is classically simulatable if its output probability distribution can be sampled up to an exponentially small additive error in classical polynomial time. Our main result is that there exists a commuting quantum circuit that is not classically simulatable unless the polynomial hierarchy collapses to the third level. This is the first formal evidence that a commuting quantum circuit is not classically simulatable even when the number of output qubits is O(log n). Then, we consider a generalized version of the circuit and clarify the condition under which it is classically simulatable. Lastly, using a proof similar to that of the main result, we provide an evidence that a slightly extended Clifford circuit is not classically simulatable.

  • Power of Quantum Computation with Few Clean Qubits.

    Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, Seiichiro Tani

    43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy     13:1-13:14  2016年  [査読有り]

  • Quantum algorithms for finding constant-sized sub-hypergraphs

    Francois Le Gall, Harumichi Nishimura, Seiichiro Tani

    THEORETICAL COMPUTER SCIENCE   609   569 - 582  2016年01月  [査読有り]

     概要を見る

    We develop a general framework to construct quantum algorithms that detect if a 3-uniform hypergraph given as input contains a sub-hypergraph isomorphic to a pre-specified constant-sized hypergraph. This framework is based on the concept of nested quantum walks recently proposed by Jeffery, Kothari and Magniez (2013) [12], and extends the methodology designed by Lee, Magniez and Santha (2013) [18] for similar problems over graphs. As applications, we obtain a quantum algorithm for finding a 4-clique in a 3-uniform hypergraph on n vertices with query complexity O(n(1.883)), and a quantum algorithm for determining if a ternary operator over a set of size n is associative with query complexity O(n(2.113)). (C) 2015 Elsevier B.V. All rights reserved.

    DOI

  • Commuting Quantum Circuits with Few Outputs are Unlikely to be Classically Simulatable

    Yasuhiro Takahashi, Seiichiro Tani, Takeshi Yamazaki, Kazuyuki Tanaka

    COMPUTING AND COMBINATORICS   9198   223 - 234  2015年  [査読有り]

     概要を見る

    We study the classical simulatability of commuting quantum circuits with n input qubits and O(log n) output qubits, where a quantum circuit is classically simulatable if its output probability distribution can be sampled up to an exponentially small additive error in classical polynomial time. Our main result is that there exists a commuting quantum circuit that is not classically simulatable unless the polynomial hierarchy collapses to the third level. This is the first formal evidence that a commuting quantum circuit is not classically simulatable even when the number of output qubits is exponentially small. Then, we consider a generalized version of the circuit and clarify the condition under which it is classically simulatable. We apply these results to examining the ability of IQP circuits to implement fundamental operations, and to examining the classical simulatability of slightly extended Clifford circuits.

    DOI

  • Impossibility of Classically Simulating One-Clean-Qubit Computation

    Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, Seiichiro Tani

       2014年09月

     概要を見る

    Deterministic quantum computation with one quantum bit (DQC1) is a restricted
    model of quantum computing where the input state is the completely mixed state
    except for a single clean qubit, and only a single output qubit is measured at
    the end of the computing. It is proved that the restriction of quantum
    computation to the DQC1 model does not change the complexity classes NQP and
    SBQP. As a main consequence, it follows that the DQC1 model cannot be
    efficiently simulated by classical computers unless the polynomial-time
    hierarchy collapses to the second level (more precisely, to AM), which answers
    the long-standing open problem posed by Knill and Laflamme under the very
    plausible complexity assumption. The argument developed in this paper also
    weakens the complexity assumption necessary for the existing impossibility
    results on classical simulation of various sub-universal quantum computing
    models, such as the IQP model and the Boson sampling.

    DOI

  • Quantum algorithms for finding constant-sized sub-hypergraphs

    François Le Gall, Harumichi Nishimura, Seiichiro Tani

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   8591   429 - 440  2014年  [査読有り]

     概要を見る

    We develop a general framework to construct quantum algorithms that detect if a 3-uniform hypergraph given as input contains a sub-hypergraph isomorphic to a prespecified constant-sized hypergraph. This framework is based on the concept of nested quantum walks recently proposed by Jeffery, Kothari and Magniez, and extends the methodology designed by Lee, Magniez and Santha for similar problems over graphs. As applications, we obtain a quantum algorithm for finding a 4-clique in a 3-uniform hypergraph on n vertices with query complexity O(n 1.883), and a quantum algorithm for determining if a ternary operator over a set of size n is associative with query complexity O(n 2.113). © 2014 Springer International Publishing Switzerland.

    DOI

  • Simpler Exact Leader Election via Quantum Reduction.

    Hirotada Kobayashi, Keiji Matsumoto, Seiichiro Tani

    Chicago J. Theor. Comput. Sci.   2014  2014年  [査読有り]

  • Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits

    Yasuhiro Takahashi, Seiichiro Tani

    2013 IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC)     168 - 178  2013年  [査読有り]

     概要を見る

    We study the quantum complexity class QNC(f)(0) of quantum operations implementable exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates. Our main result is that the quantum OR operation is in QNC(f)(0), which is an affirmative answer to the question of Hoyer and. Spalek. In sharp contrast to the strict hierarchy of the classical complexity classes: NC0 (sic) AC(0) (sic) TC0, our result with Hoyer and. Spalek's one implies the collapse of the hierarchy of the corresponding quantum ones: QNC(f)(0) = QAC(f)(0) = QTC(f)(0). Then, we show that there exists a constant-depth subquadraticsize quantum circuit for the quantum threshold operation. This allows us to obtain a better bound on the size difference between the QNC(f)(0) and QTC(f)(0) circuits for implementing the same quantum operation. Lastly, we show that, if the quantum Fourier transform modulo a prime is in QNC(f)(0), there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a QNC(f)(0) oracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a QNC(f)(0) circuit with gates for the quantum Fourier transform.

    DOI DOI2

  • Exact quantum algorithms for the leader election problem

    Seiichiro Tani, Hirotada Kobayashi, Keiji Matsumoto

    ACM Transactions on Computation Theory   4 ( 1 ) 1:1-1:24  2012年03月  [査読有り]

     概要を見る

    This article gives a separation between quantum and classical models in pure (i.e., noncryptographic) computing abilities with no restriction on the amount of available computing resources, by considering the exact solvability of the leader election problem in anonymous networks, a celebrated unsolvable problem in classical distributed computing. The goal of the leader election problem is to elect a unique leader from among distributed parties. In an anonymous network, all parties with the same number of communication links are identical. It is well-known that no classical algorithm can exactly solve (i.e., in bounded time without error) the leader election problem in anonymous networks, even if the number of parties is given. This article devises a quantum algorithm that, if the number of parties is given, exactly solves the problem for any network topology in polynomial rounds with polynomial communication/time complexity with respect to the number of parties, when the parties are connected with quantum communication links and they have the ability of quantum computing. Our algorithm works even when only an upper bound of the number of parties is given. In such a case, no classical algorithm can solve the problem even under the zero-error setting, the setting in which error is not allowed but running time may be unbounded. © 2012 ACM 1942-3462/2012/03-ART1 $10.00.

    DOI

  • Compression of View on Anonymous Networks-Folded View-

    Seiichiro Tani

    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS   23 ( 2 ) 255 - 262  2012年02月  [査読有り]

     概要を見る

    View is a labeled directed graph containing all information about the network that a party can learn by exchanging messages with its neighbors. View can be used to solve distributed problems on an anonymous network (i.e., a network that does not guarantee that every party has a unique identifier). This paper presents an algorithm that constructs views in a compressed form on an anonymous n-party network of any topology in at most 2n rounds with O(n(6) log n) bit complexity, where the time complexity (i.e., the number of local computation steps per party) is O(n(6) log n). This is the first view-construction algorithm that runs in O(n) rounds with polynomial bits complexity. The paper also gives an algorithm that counts the number of nonisomorphic views in the network in O(n(6) log n) time complexity if a view is given in the compressed form. These algorithms imply that some well-studied problems, including the leader election problem, can deterministically be solved in O(n) rounds with polynomial bit and time complexity on an anonymous n-party network of any topology.

    DOI

  • Reconstructing strings from substrings with quantum queries

    Richard Cleve, Kazuo Iwama, François Le Gall, Harumichi Nishimura, Seiichiro Tani, Junichi Teruyama, Shigeru Yamashita

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   7357   388 - 397  2012年  [査読有り]

     概要を見る

    This paper investigates the number of quantum queries made to solve the problem of reconstructing an unknown string from its substrings in a certain query model. More concretely, the goal of the problem is to identify an unknown string S by making queries of the following form: "Is s a substring of S?", where s is a query string over the given alphabet. The number of queries required to identify the string S is the query complexity of this problem. First we show a quantum algorithm that exactly identifies the string S with at most queries, where N is the length of S. This contrasts sharply with the classical query complexity N. Our algorithm uses Skiena and Sundaram's classical algorithm and the Grover search as subroutines. To make them effectively work, we develop another subroutine that finds a string appearing only once in S, which may have an independent interest. We also prove two lower bounds. The first one is a general lower bound of , which means we cannot achieve a query complexity of O(N 1∈-∈ε ) for any constant ε. The other one claims that if we cannot use queries of length roughly between logN and 3 logN, then we cannot achieve a query complexity of any sublinear function in N. © 2012 Springer-Verlag.

    DOI DOI2

  • The One-Way Communication Complexity of Subgroup Membership.

    Scott Aaronson, François Le Gall, Alexander Russell, Seiichiro Tani

    Chicago J. Theor. Comput. Sci.   2011  2011年  [査読有り]

  • QUANTUM ADDITION CIRCUITS AND UNBOUNDED FAN-OUT

    Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro

    QUANTUM INFORMATION & COMPUTATION   10 ( 9-10 ) 872 - 890  2010年09月  [査読有り]

     概要を見る

    We first show how to construct an O(n)-depth O(n)-size quantum circuit for addition of two n-bit binary numbers with no ancillary qubits. The exact size is 7n - 6, which is smaller than that of any other quantum circuit ever constructed for addition with no ancillary qubits. Using the circuit, we then propose a method for constructing an O(d(n))-depth O(n)-size quantum circuit for addition with O(n/d(n)) ancillary qubits for any d(n) = Omega(log n). If we are allowed to use unbounded fan-out gates with length O(n(epsilon)) for an arbitrary small positive constant E, we can modify the method and construct an O(e(n))-depth O(n)-size circuit with o(n) ancillary qubits for any e(n) = Omega(log* n). In particular, these methods yield efficient circuits with depth O(log n) and with depth O(log* n), respectively. We apply our circuits to constructing efficient quantum circuits for Shor's discrete logarithm algorithm.

  • THE QUANTUM QUERY COMPLEXITY OF CERTIFICATION

    Andris Ambainis, Andrew M. Childs, Francois Le Gall, Seiichiro Tani

    QUANTUM INFORMATION & COMPUTATION   10 ( 3-4 ) 181 - 189  2010年03月  [査読有り]

     概要を見る

    We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NANDformula. We show that the query complexity is circle minus(d((k+1)/2)) for 0-certificates, and (circle minus) over tilde (d(k/2)) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is (O) over tilde (d((k+1)/2)). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.

  • Claw finding algorithms using quantum walk

    Seiichiro Tani

    THEORETICAL COMPUTER SCIENCE   410 ( 50 ) 5285 - 5297  2009年11月  [査読有り]

     概要を見る

    The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. Given two functions, f and g, with domain sizes N and M(N &lt;= M), respectively, and the same range, the goal of the problem is to find x and y such that f (x) = g(y). This problem has been considered in both quantum and classical settings in terms of query complexity. This paper describes an optimal algorithm that uses quantum walk to solve this problem. Our algorithm can be slightly modified to solve the more general problem of finding a tuple consisting of elements in the two function domains that has a prespecified property. it can also be generalized to find a claw of k functions for any constant integer k &gt; 1, where the domain sizes of the functions may be different. (C) 2009 Elsevier B.V. All rights reserved.

    DOI

  • Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size

    Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita

      abs/0908.2468  2009年08月

     概要を見る

    This paper considers the query complexity of the functions in the family<br />
    F_{N,M} of N-variable Boolean functions with onset size M, i.e., the number of<br />
    inputs for which the function value is 1, where 1&lt;= M &lt;= 2^{N}/2 is assumed<br />
    without loss of generality because of the symmetry of function values, 0 and 1.<br />
    Our main results are as follows: (1) There is a super-linear gap between the<br />
    average-case and worst-case quantum query complexities over F_{N,M} for a<br />
    certain range of M. (2) There is no super-linear gap between the average-case<br />
    and worst-case randomized query complexities over F_{N,M} fo...

  • Multi-Party Quantum Communication Complexity with Routed Messages

    Seiichiro Tani, Masaki Nakanishi, Shigeru Yamashita

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS   E92D ( 2 ) 191 - 199  2009年02月  [査読有り]

     概要を見る

    This paper describes a general quantum lower bounding technique for the communication complexity of a function that depends on the inputs given to two parties connected via paths, which may be shared with other parties, on a network of any topology. The technique can also be employed to obtain a lower-bound of the quantum communication complexity of some functions that depend on the inputs distributed over all parties on the network. As a typical application, we apply our technique to the distinctness problem of deciding whether there are a pair of parties with identical inputs, on a k-party ring; almost matching upper bounds are also given.

    DOI

  • Brief Announcement: Exactly Electing a Unique Leader is not Harder than Computing Symmetric Functions on Anonymous Quantum Networks

    Hirotada Kobayashi, Keiji Matsumoto, Seiichiro Tani

    PODC&apos;09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING     334 - 335  2009年  [査読有り]

     概要を見る

    This paper proves that, if quantum communication and computation are available and the number of parties is given, the leader election problem can exactly (i.e., without error in bounded time) be solved with at most the same complexity up to a constant factor as that of exactly computing certain symmetric functions for a distributed and superposed input on an anonymous network of any unknown topology. Together with a novel quantum algorithm that computes a certain symmetric function, this characterization yields a quantum leader election algorithm that is more efficient than existing algorithms.

    DOI

  • Experimental demonstration of quantum leader election in linear optics

    Yuta Okubo, Xiang-Bin Wang, Yun-Kun Jiang, Seiichiro Tani, Akihisa Tomita

    Physical Review A - Atomic, Molecular, and Optical Physics   77 ( 3 )  2008年03月  [査読有り]

     概要を見る

    Linear optics is a promising candidate to enable the construction of quantum computers. A number of quantum protocols gates based on linear optics have been demonstrated. However, it is well known that these gates are nondeterministic and that higher order nonlinearity is necessary for deterministic operations. We found the quantum leader election protocol can be operated deterministically only with linear optics, and we have demonstrated the nearly deterministic operation which overcomes classical limit. © 2008 The American Physical Society.

    DOI

  • Quantum Query Complexity of Boolean Functions with Small On-Sets

    Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita

    ALGORITHMS AND COMPUTATION, PROCEEDINGS   5369   907 - +  2008年  [査読有り]

     概要を見る

    The main objective of this paper is to show that the quantum query complexity Q(f) of an N-bit Boolean function f is bounded by a function of a simple and natural parameter, i.e., M = vertical bar{x vertical bar f(x) = 1}vertical bar or the size of f's on-set. We prove that: (i) For poly(N) &lt;= M &lt;= 2(Nd) for some constant 0 &lt; d &lt; 1, the upper bound of Q(f) is O(root N log M/ log N). This bound is tight, namely there is Boolean function f such that Q(f) = Omega(root N log M/ log N). (ii) For the same range of M, the (also tight) lower bound of Q(f) is Omega(root N). (iii) The average value of Q(f) is bounded from above and below by Q(f) = O(log M + root N) and Q(f) = Omega(log M/ log N + root N), respectively. The first bound gives a simple way of bounding the quantum query complexity of testing some graph properties. In particular, it is proved that the quantum query complexity of planarity testing for a graph with n vertices Theta(N-3/4) where N = n(n-1)/2.

    DOI

  • Multi-party quantum communication complexity with routed messages

    Seiichiro Tani, Masaki Nakanishi, Shigeru Yamashita

    COMPUTING AND COMBINATORICS, PROCEEDINGS   5092   180 - 190  2008年  [査読有り]

     概要を見る

    This paper describes a general quantum lower bounding technique for the communication complexity of a function that depends on the inputs given to two parties connected via paths, which may be shared with other parties, on a network of any topology. The technique can also be employed to obtain a lower-bound of the quantum communication complexity of some functions that depend on the inputs distributed over all parties on the network. As a typical application, we apply our technique to the distinctness problem of deciding whether there are at least two parties with identical inputs, on a k-party ring; almost matching upper bounds are also given.

    DOI

  • 量子分散コンピューティング

    谷 誠一郎, ルガル フランソワ

    電子情報通信学会論文誌. A, 基礎・境界 = The transactions of the Institute of Electronics, Information and Communication Engineers. A   90 ( 5 ) 393 - 402  2007年05月  [査読有り]

     概要を見る

    ネットワークで接続された複数の計算機が協調して行う計算を分散コンピューティングと呼び,古典計算では長い歴史をもつ研究分野である.最近,複数の量子計算機が量子通信路を介して協調計算を行う量子分散コンピューティングが注目されており,その効率性について,古典分散コンピューティングと比較検討されている.本論文では,これまでの基本的な結果を振り返り,更に最近の成果についても触れる.

    CiNii

  • An improved claw finding algorithm using quantum walk

    Seiichiro Tani

    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2007, PROCEEDINGS   4708   536 - 547  2007年  [査読有り]

     概要を見る

    for any constant integer k &gt; 1, where the domains of the functions may have different size.The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. For given two functions, f and g, as an oracle which have domains of size N and M (N &lt;= M), respectively, and the same range, the goal of the problem is to find x and y such that f (x) = g(y). This paper describes a quantum-walk-based algorithm that solves this problem; it improves the previous upper bounds. Our algorithm can be generalized to find a claw of k functions for any constant integer k &gt; 1, where the domains of the functions may have different size.

  • Flexcast による段階的導入に優れたマルチキャストシステムの設計と実装

    井上 武, 谷 誠一郎, 高橋 宏和, 湊 真一, 宮崎 敏明, 豊島 鑑

    電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理 = The transactions of the Institute of Electronics, Information and Communication Engineers. D-I   88 ( 2 ) 272 - 291  2005年02月  [査読有り]

     概要を見る

    IP multicastは, これまで10年以上にわたって研究開発が進められてきたが, インターネット全域に広く展開されるには至っていない.この原因の一つとして, IP multicastを使ったマルチキャストシステムは, 初期投資が大きいという点が考えられる.FlexcastはIP multicastと同様にルータで分岐を行う方式であるが, マルチキャスト機能をネットワーク層からより上位の層へと移したため, 部分的な導入でサービスを開始できるという特徴をもつ.我々はこのようなFlexcastの特徴を使って, 少ない設備投資でサービスを開始でき, 需要に合わせて拡張可能なマルチキャストシステムを開発した.Flexcastルータの開発にあたっては, WWW検索システムやGRID computingで大きな成果を挙げているPCクラスタを応用し, 初期投資の抑制と高い拡張性を実現するとともに, ネットワーク装置に求められる高い可用性も実現した.グループ管理システムの開発では, IP multicastとの互換性を維持し, 既存アプリケーションの利用を可能とすることで, 開発コストを抑制した.更に, IP multicastにおいて長年の懸案となっていたグループアドレス管理に関するスケーラビリティ問題を, 管理権限を局所化することにより解決した.最後に, 市販PCに実装して評価実験を行い, 本提案システムがGbit/sレベルの転送能力を有しており, また, 高い可用性を備えることを明らかにした.

    CiNii

  • Exact quantum algorithms for the leader election problem

    S Tani, H Kobayashi, K Matsumoto

    STACS 2005, PROCEEDINGS   3404   581 - 592  2005年  [査読有り]

     概要を見る

    It is well-known that no classical algorithm can solve exactly (i.e., in bounded time without error) the leader election problem in anonymous networks. This paper gives two quantum algorithms that, when the parties are connected by quantum communication links, can exactly solve the problem for any network topology in polynomial rounds and polynomial communication/time complexity with respect to the number of parties. Our algorithms work well even in the case where only the upper bound of the number of parties is given.

    DOI

  • Design and implementation of advanced multicast router based on cluster computing

    T Inoue, S Tani, F Takahashi, SI Minato, T Miyazaki, K Toyoshima

    11TH INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL I, PROCEEDINGS     328 - 334  2005年  [査読有り]

     概要を見る

    This paper presents the design principles of an advanced multicast router and evaluates its performance in experiments. Our multicast router features cluster computing, which has been used to develop a high performance search engine and GRID computing. The router consists of a small-scale cluster attached to a regular router While it is not a standard router architecture, it offers high extensibility and availability without much investment. Our design is based on the new multicast technology called Flexcast [10], which naturally supports incremental deployment of the multicast infrastructure unlike IP multicast. In Flexcast, multicast packets are replicated at each router like IP multicast. However Flexcast is implemented in the layer above the network layer; the multicast stream is transmitted by unicast between routers that support Flexcast, and bypasses routers that do not support it. The goal of this paper is to bring the concept of incremental deployment to a multicast router as well as the protocol, by means of cluster computing. We implemented several routers on Linux PCs and tested them in experiments. The results of the experiments reveal that forwarding performance and availability are greatly enhanced by cluster computing. Our efforts provide the economy, efficiency, and extensibility needed to realize the multicast infrastructure.

    DOI

  • Wide-Area Multicasting based on Flexcast: Toward the Ubiquitous Network

    Takeru Inoue, Seiichiro Tani, Katsuhiro Ishimaru, Shin-ichi Minato, Toshiaki Miyazaki

    Proc. of the 5th Asia-Pacific Symposium on Information and Telecommunication Technologies (APSITT)     301 - 306  2003年11月  [査読有り]

    CiNii

  • A Randomized Online Algorithm for the File Caching Problem

    TANI Seiichiro, MIYAZAKI Toshiaki

    IEICE transactions on information and systems   86 ( 4 ) 686 - 697  2003年04月  [査読有り]

     概要を見る

    Caching web files reduces user response time as well as network traffic. When implementing caches, the file caching problem must be addressed ; the problem is how to determine which files should be evicted from a cache when there is insufficient space for storing a new file so that the sum of the mis-hit (fault) file costs is minimized. Greedy-Dual-Size (GDS) is the best online algorithm in terms of competitiveness, i. e., k/(k-h+1)-competitive, where k and h are the storage space of, respectively, GDS and an optimal offline algorithm. GDS performs very well even in trace-driven simulations. The worst-case time taken to service a request is another important measure for online file caching algorithms since slow response times render caching meaningless from the client's view point. This paper proposes a fast randomized k/(k-h+1)-competitive algorithm that performs in O(2^<log k>) time per file eviction or insertion, whereas GDS takes O(log k) time, where 2^<log k> is a much slower increasing function than log k. To confirm its practicality, we conduct trace driven simulations. Experimental results show that our algorithm attains only slightly worse byte hit rates and sufficiently large reduced latency in comparison with GDS, and our algorithm is a good candidate for caches requiring high-speed processing such as second-level caches in the large networks.

    CiNii

  • Flexcast: Self-organizing multicast technology

    Seiichiro Tani, Toshiaki Miyazaki, Noriyuki Takahashi, Shin Ichi Minato

    NTT R and D   52 ( 3 ) 213 - 222  2003年

     概要を見る

    The World Wide Web (WWW) is a tool that lets individuals broadcast contents, and streaming data is rapidly increasing its percentage of the total traffic carried. Conventional broadcast techniques, however, waste too much bandwidth because the servers send streaming data directly to each recipient, even if there are many of them. This paper proposes a new IP-unicast-based multicast technology, called "Flexcast." Flexcast autonomously updates the optimal delivery tree when recipients emerge or disappear. Flexcast also maintains the optimal delivery tree in spite of user host mobility and/or changes in IP routing; the Flexcast protocol is so simple that it is extremely scalable. Its validity and feasibility are confirmed by a bench-test.

  • An Approach to Adaptive Network

    ISHIHARA Shinya, MIYAZAKI Toshiaki, TAKAHARA Atsushi, TANI Seiichiro

    IEICE transactions on information and systems   85 ( 5 ) 839 - 846  2002年05月  [査読有り]

     概要を見る

    This paper describes the concept of an adaptive network, that is, a network environment that can rapidly and autonomously adapt its bebavior according to network conditions and traffic status. The user interface of the adaptive network can access any resource in the network as a memory-mapped I/O device, as if it were attached to the local bus of the user's PC. This network concept has several benefits. From the application development viewpoint, no network related programming is required, and applications do not have to be modified even if the network topologies and protocols are changed. Network maintenance and upgrading can be done anytime without having to worry about the application users, because the network itself is concealed from the applications. In addition, the reconfigurable hardware technology functions as an autonomous network control through the use of a lower-layer protocol. We developed a testbed that makes heterogeneous resources available to users and used it to demonstrate the feasibility of our concept by implementing and running some applications over it.

    CiNii

  • A Design Framework for Online Algorithms Solving the Object Replacement Problem

    TANI Seiichiro, MIYAZAKI Toshiaki

    IEICE transactions on information and systems   84 ( 9 ) 1135 - 1143  2001年09月  [査読有り]

     概要を見る

    Network caches reduce network traffic as well as user response time. When implementing network caches, the object replacement problem is one of the core problems ; The problem is to determine which objects should be evicted from a cache when there is insufficient space. This paper first formalizes the problem and gives a simple but sufficient condition for deterministic online algorithms to be competitive. Based on the condition, a general framework to make a non-competitive algorithm competitive is constructed. As an application of the framework, an online algorithm, called Competitive_SIZE, is proposed. Both event-driven and trace-driven simulations show that Competitive_SIZE is better than previously proposed algorithms such as LRU (Least Recently Used).

    CiNii

  • Infrastructure technology for adaptive network: Active network

    Toshiaki Miyazaki, Noriyuki Takahashi, Takahiro Murooka, Seiichiro Tani

    NTT R and D   50 ( 12 ) 1002 - 1010  2001年

     概要を見る

    It is very important to realize the adaptive network that can dynamically adapt itself to users' needs and data traffic. We are developing an Active Network (AN) environment as a basic mechanism to realize such a network. AN is a network technology that enables us to introduce new services easily by attaching programs to the packets and evaluating the programs at each router. In this paper, after introducing our AN environment, an active router that is the most important part realizing the AN is described. In addition, a streaming multicast application using the AN is presented.

  • Adaptive Stream Multicast Based on IP Unicast and Dynamic Commercial Attachment Mechanism: An Active Network Implementation.

    Seiichiro Tani, Toshiaki Miyazaki, Noriyuki Takahashi

    Active Networks, IFIP-TC6 Third International Working Conference, IWAN 2001, Philadelphia, PA, USA, September 30-October 2, 2001, Proceedings   2207   116 - 133  2001年  [査読有り]

    DOI

  • Virtual BUS: A Network Technology for Setting up Distributed Resources in Your Own Computer.

    Toshiaki Miyazaki, Atsushi Takahara, Shinya Ishihara, Seiichiro Tani, Takahiro Murooka, Tomoo Fukazawa, Mitsuo Teramoto, Kazuyoshi Matsuhiro

    Proceedings of the 14th International Parallel & Distributed Processing Symposium (IPDPS'00), Cancun, Mexico, May 1-5, 2000     535 - 540  2000年  [査読有り]

    DOI

  • Efficient path selection for delay testing based on path clustering

    S Tani, M Teramoto, T Fukazawa, K Matsuhiro

    JOURNAL OF ELECTRONIC TESTING-THEORY AND APPLICATIONS   15 ( 1-2 ) 75 - 85  1999年08月  [査読有り]

     概要を見る

    In this paper, we introduce a way of modeling the differences between the calculated delays and the real delays, and propose an efficient path selection method for path delay testing based on the model. Path selection is done by judging which of two paths has the larger real delay by taking into account the ambiguity of calculated delay, caused by imprecise delay modeling as well as process disturbances. In order to make precise judgment under this ambiguity, the delays of only the unshared segments of the two paths are evaluated. This is because the shared segments are presumed to have the same real delays on both paths.
    The experiments used the delays of gates and interconnects, which were calculated from the layout data of ISCAS85 benchmark circuits using a real cell library. Experimental results show the method selects only about one percent of the paths selected by the most popular method.

    DOI

  • Virtual BUS: A simple implementation of an effortless networking system based on PVM

    Shinya Ishihara, Seiichiro Tani, Atsushi Takahara

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   1697   461 - 468  1999年  [査読有り]

     概要を見る

    This paper describes a simple implementation of an effortless networking system. On the analogy of the conventional computer’s bus architecture, we propose the concept “Virtual BUS”. In our approach, an application virtually expands its own local bus into the network and accesses various distributed computing resources as if they are on the local bus. We present a light-weight experimental system using the PVM message passing interface and evaluate our approach.

    DOI

  • Virtual BUS: An Easy-to-Use Environment for Distributed Resources.

    Atsushi Takahara, Seiichiro Tani, Shinya Ishihara, Toshiaki Miyazaki, Mitsuo Teramoto, Tomoo Fukazawa, Kazuyoshi Matsuhiro

    Proceedings 26th Conference on Local Computer Networks, Lowell, Massachusetts, USA, 17-20 October, 1999     62 - 70  1999年  [査読有り]

    DOI

  • Efficient path selection for delay testing based on partial path evaluation

    S Tani, M Teramoto, T Fukazawa, K Matsuhiro

    16TH IEEE VLSI TEST SYMPOSIUM, PROCEEDINGS     188 - 193  1998年  [査読有り]

     概要を見る

    In this paper, we propose an efficient path selection method for path delay testing. The proposed method selects a very small set of paths for delay testing that covers all paths. Path selection is done by judging which of two paths has the larger real delay by taking into account the ambiguity of calculated delay, caused by imprecise delay modeling as well as process disturbance. In order to make precise judgement under this ambiguity, the delays of only unshared segments between the two paths are evaluated. This is because the shared segments are presumed to have the same real delays on both paths. Experimental results show the method can select about one percent of the paths selected by a conventional method without decreasing fault coverage.

    DOI

  • The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram

    TANI Seiichiro, HAMAGUCHI Kiyoharu, YAJIMA Shuzo

    IEICE transactions on information and systems   79 ( 4 ) 271 - 281  1996年04月  [査読有り]

     概要を見る

    An ordered binary decision diagram (OBDD) is a directed acyclic graph for representing a Boolean function. OBDDs are widely used in various areas which require Boolean function manipulation, since they can represent efficiently many practical Boolean functions and have other desirable properties. However, there is very little theoretical research on the complexity of constructing an OBDD. In this paper, we prove that the optimal variable ordering problem of a shared BDD is NP-complete, and briefly discuss the approximation hardness of this problem and related OBDD problems.

    CiNii

  • Computing the Tutte Polynomial of a Graph of Moderate Size.

    Kyoko Sekine, Hiroshi Imai, Seiichiro Tani

    Algorithms and Computation, 6th International Symposium, ISAAC '95, Cairns, Australia, December 4-6, 1995, Proceedings   1004   224 - 233  1995年  [査読有り]

    DOI CiNii

  • Output-size sensitiveness of OBDD construction through maximal independent set problem

    K Hayase, K Sadakane, S Tani

    COMPUTING AND COMBINATORICS   959   229 - 234  1995年  [査読有り]

     概要を見る

    This paper investigates output-size sensitiveness of construction of OBDD by analyzing the maximal independent set problem of a graph, which would give several insights to efficient manipulation of Boolean functions by OBDD and graph theory.

    DOI

  • A Reordering Operation for an Ordered Binary Decision Diagram and an Extended Framework for Combinatorics of Graphs.

    Seiichiro Tani, Hiroshi Imai

    Algorithms and Computation, 5th International Symposium, ISAAC '94, Beijing, P. R. China, August 25-27, 1994, Proceedings     575 - 583  1994年  [査読有り]

    DOI CiNii

  • The Complexity of the Optimal Variable Ordering Problems of Shared Binary Decision Diagrams.

    Seiichiro Tani, Kiyoharu Hamaguchi, Shuzo Yajima

    Algorithms and Computation, 4th International Symposium, ISAAC '93, Hong Kong, December 15-17, 1993, Proceedings     389 - 398  1993年  [査読有り]

    DOI CiNii

▼全件表示

講演・口頭発表等

  • 近似精度において最適な確率的量子コンパイラ

    秋笛清石, 加藤 豪, 谷 誠一郎

    電子情報通信学会 技術研究報告 量子情報技術研究会(QIT)  

    発表年月: 2022年12月

    開催年月:
    2022年12月
     
     
  • Computational self-testing for entangled magic states

    A. Mizutani, Y. Takeuchi, R. Hiromasa, Y. Aikawa, S. Tani

    Beyond IID in Information Theory 10 (Beyondiid10)  

    発表年月: 2022年09月

    開催年月:
    2022年09月
     
     
  • Space-Bounded Unitary Quantum Computation with Postselection

    Seiichiro Tani

    47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)  

    発表年月: 2022年08月

    開催年月:
    2022年08月
     
     
  • 計算量的仮定に基づくエンタングルしたマジック状態のセルフテスト

    水谷 明博, 竹内 勇貴, 廣政 良, 相川 勇輔, 谷 誠一郎

    電子情報通信学会 技術研究報告 量子情報技術(QIT)  

    発表年月: 2022年05月

    開催年月:
    2022年05月
     
     
  • Halving the length of approximate classical representations of pure quantum states with probabilistic encoding

    Seiseki Akibue, Go Kato, Seiichiro Tani

    25th Annual Conference on Quantum Information Processing  

    発表年月: 2022年03月

    開催年月:
    2022年03月
     
     
  • Efficiently generating ground states is hard for postselected quantum computation

    Yuki Takeuchi, Yasuhiro Takahashi, Seiichiro Tani

    25th Annual Conference on Quantum Information Processing  

    発表年月: 2022年03月

    開催年月:
    2022年03月
     
     
  • NISQ計算の分割統治による検証

    竹内 勇貴, 高橋 康博, 森前 智行, 谷 誠一郎

    電子情報通信学会 技術研究報告 量子情報技術(QIT)  

    発表年月: 2021年12月

    開催年月:
    2021年11月
    -
    2021年12月
  • 確率的符号化を用いた純粋量子状態の古典表現の圧縮

    秋笛清石, 加藤 豪, 谷 誠一郎

    電子情報通信学会 技術研究報告 量子情報技術研究会(QIT)  

    発表年月: 2021年11月

    開催年月:
    2021年11月
    -
    2021年12月
  • Hardness of efficiently generating ground states in postselected quantum computation

    Yuki Takeuchi, Yasuhiro Takahashi, Seiichiro Tani

    21th Asian Quantum Information Science Conference (AQIS 2021)  

    発表年月: 2021年09月

    開催年月:
    2021年09月
     
     
  • 量子計算を古典委託するための合理的なサムチェックプロトコル

    竹内 勇貴, 森前 智行, 谷 誠一郎

    電子情報通信学会 技術研究報告 コンピュテーション (COMP)   (オンライン) 

    発表年月: 2021年08月

    開催年月:
    2021年08月
     
     
  • Classically Simulating Quantum Circuits with Local Depolarizing Noise

    Yasuhiro Takahashi, Yuki Takeuchi, Seiichiro Tani

    電子情報通信学会 技術研究報告 コンピュテーション (COMP)   (オンライン) 

    発表年月: 2021年03月

    開催年月:
    2021年03月
    -
    2021年08月
  • Efficiently generating ground states is hard for postselected quantum computation

    Yuki Takeuchi, Yasuhiro Takahashi, Seiichiro Tani

    発表年月: 2021年07月

    開催年月:
    2021年07月
     
     
  • Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams

    Seiichiro Tani

    16th Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC 2021)  

    発表年月: 2021年07月

    開催年月:
    2021年07月
     
     
  • Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams

    Seiichiro Tani

    情報処理学会 研究報告 量子ソフトウェア(QS)  

    発表年月: 2021年06月

    開催年月:
    2021年06月
     
     
  • Hardness of efficiently generating ground states in postselected quantum computation

    Yuki Takeuchi, Yasuhiro Takahashi, Seiichiro Tani

    情報処理学会 研究報告 量子ソフトウェア(QS)  

    発表年月: 2021年06月

    開催年月:
    2021年06月
     
     
  • Classically Simulating Quantum Circuits with Local Depolarizing Noise

    Yasuhiro Takahashi, Yuki Takeuchi, Seiichiro Tani

    情報処理学会 研究報告 量子ソフトウェア(QS)  

    発表年月: 2021年06月

    開催年月:
    2021年06月
     
     
  • Classically Simulating Quantum Circuits with Local Depolarizing Noise

    Yasuhiro Takahashi, Yuki Takeuchi, Seiichiro Tani

    24th Annual Conference on Quantum Information Processing (QIP 2021)  

    発表年月: 2021年02月

    開催年月:
    2021年02月
     
     
  • 二分決定グラフの最適変数順序を見つける量子アルゴリズム

    谷 誠一郎

    電子情報通信学会 技術研究報告 量子情報技術(QIT)  

    発表年月: 2020年12月

    開催年月:
    2020年12月
     
     
  • 任意の分離可能状態を生成できる量子もつれ破壊通信路の指数的複雑性 ~ Disentangler 仮説ヘの応用 ~

    秋笛 清石, 加藤 豪, 谷 誠一郎

    電子情報通信学会 技術研究報告 量子情報技術(QIT)  

    発表年月: 2020年12月

    開催年月:
    2020年12月
     
     
  • Polylog-overhead fault-tolerant measurement-based quantum computation by homodyne detection

    Hayata Yamasaki, Kosuke Fukui, Yuki Takeuchi, Seiichiro Tani, Masato Koashi

    15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)  

    発表年月: 2020年06月

    開催年月:
    2020年06月
     
     
  • Classically Simulating Quantum Circuits with Local Depolarizing Noise.

    Yasuhiro Takahashi, Yuki Takeuchi, Seiichiro Tani

    Proc. 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)   Schloss Dagstuhl - Leibniz-Zentrum für Informatik  

    発表年月: 2020年

    開催年月:
    2020年
     
     
  • Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams.

    Seiichiro Tani

    Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), Leibniz International Proceedings in Informatics (LIPIcs),  

    発表年月: 2020年

    開催年月:
    2020年
     
     
  • 古典クライアントによるブラインド量子計算の不可能性

    森前 智行, 西村 治道, 竹内 勇貴, 谷 誠一郎

    電子情報通信学会 技術研究報告 量子情報技術(QIT)  

    発表年月: 2019年11月

    開催年月:
    2019年11月
     
     
  • 量子計算を古典委託するための合理的なサムチェックプロトコル

    竹内 勇貴, 森前 智行, 谷 誠一郎

    電子情報通信学会 量子情報技術研究会 (QIT 41)  

    発表年月: 2019年11月

    開催年月:
    2019年11月
     
     
  • 分離可能状態空間への量子写像の複雑性

    秋笛 清石, 加藤 豪, 谷 誠一郎

    電子情報通信学会 技術研究報告 量子情報技術(QIT)  

    発表年月: 2019年11月

    開催年月:
    2019年11月
     
     
  • Improved quantum multicollision-finding algorithm

    Akinori Hosoyamada, Yu Sasaki, Seiichiro Tani, Keita Xagawa

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   Springer  

    発表年月: 2019年

    開催年月:
    2019年
     
     

     概要を見る

    © Springer Nature Switzerland AG 2019. The current paper improves the number of queries of the previous quantum multi-collision finding algorithms presented by Hosoyamada et al. at Asiacrypt 2017. Let an l-collision be a tuple of l distinct inputs that result in the same output of a target function. In cryptology, it is important to study how many queries are required to find l-collisions for random functions of which domains are larger than ranges. The previous algorithm finds an l-collision for a random function by recursively calling the algorithm for finding (l-l) -collisions, and it achieves the average quantum query complexity of (Formula presented), where N is the range size of target functions. The new algorithm removes the redundancy of the previous recursive algorithm so that different recursive calls can share a part of computations. The new algorithm finds an l-collision for random functions with the average quantum query complexity of (Formula presented), which improves the previous bound for all l ≥3 (the new and previous algorithms achieve the optimal bound for l=2). More generally, the new algorithm achieves the average quantum query complexity of (Formula presented) for a random function (Formula presented) such that (Formula presented) for any (Formula presented). With the same query complexity, it also finds a multiclaw for random functions, which is harder to find than a multicollision.

  • Power of Uninitialized Qubits in Shallow Quantum Circuits.

    Yasuhiro Takahashi, Seiichiro Tani

    35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France   Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik  

    発表年月: 2018年

    開催年月:
    2018年
     
     
  • Power of Quantum Computation with Few Clean Qubits.

    Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, Seiichiro Tani

    43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy   Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik  

    発表年月: 2016年

    開催年月:
    2016年
     
     
  • Commuting Quantum Circuits with Few Outputs are Unlikely to be Classically Simulatable

    Yasuhiro Takahashi, Seiichiro Tani, Takeshi Yamazaki, Kazuyuki Tanaka

    COMPUTING AND COMBINATORICS   SPRINGER-VERLAG BERLIN  

    発表年月: 2015年

    開催年月:
    2015年
     
     

     概要を見る

    We study the classical simulatability of commuting quantum circuits with n input qubits and O(log n) output qubits, where a quantum circuit is classically simulatable if its output probability distribution can be sampled up to an exponentially small additive error in classical polynomial time. Our main result is that there exists a commuting quantum circuit that is not classically simulatable unless the polynomial hierarchy collapses to the third level. This is the first formal evidence that a commuting quantum circuit is not classically simulatable even when the number of output qubits is exponentially small. Then, we consider a generalized version of the circuit and clarify the condition under which it is classically simulatable. We apply these results to examining the ability of IQP circuits to implement fundamental operations, and to examining the classical simulatability of slightly extended Clifford circuits.

  • Reconstructing strings from Substrings with Quantum Queries

    CLEVE RICHARD, IWAMA KAZUO, LE GALL FRANCOIS, NISHIMURA Harumichi, TANI Seiichiro, TERUYAMA JUNICHI, YAMASHITA Shigeru

    電子情報通信学会技術研究報告. COMP, コンピュテーション   一般社団法人電子情報通信学会  

    発表年月: 2012年04月

    開催年月:
    2012年04月
     
     

     概要を見る

    This paper investigates the number of quantum queries made to solve the problem of reconstructing an unknown string from its substrings in a certain query model. More concretely, the goal of the problem is to identify an unknown string S by making queries of the following form: "Is s a substring of S?", where s is a query string over the given alphabet. The number of queries required to identify the string S is the query complexity of this problem. First we show a quantum algorithm that exactly identifies the string S with at most 3/4 N + o(N) queries, where N is the length of S. This contrasts sharply with the classical query complexity N. Our algorithm uses Skiena and Sundaram's classical algorithm and the Grover search as subroutines. To make them effectively work, we develop another subroutine that finds a string appearing only once in S, which may have an independent interest. We also prove that any bounded-error quantum algorithm needs Ω(N/log^2N ) queries. For this, we introduce another query model and obtain a lower bound for this model with the adversary method, from which bound we get the desired lower bound in the original query model.

  • DS-1-11 Reconstructing Strings from Substrings with Quantum Query

    Cleve Richard, Iwama Kazuo, Le Gal Francois, Nishimura Harumichi, Tani Seiichiro, Teruyama Junichi, Yamashita Shigeru

    電子情報通信学会総合大会講演論文集   一般社団法人電子情報通信学会  

    発表年月: 2011年02月

    開催年月:
    2011年02月
     
     
  • Quantum Communication Protocols with Public Coins (アルゴリズム(AL) Vol.2009-AL-126)

    TANI SEIICHIRO, NAKANISHI MASAKI, YAMASHITA SHIGERU

    情報処理学会研究報告. AL, アルゴリズム研究会報告   情報処理学会  

    発表年月: 2009年09月

    開催年月:
    2009年09月
     
     

     概要を見る

    This paper studies the model of quantum protocols with classical public coins, and shows its application to quantum communication complexity of some functions. The paper first proves, by carefully combining quantum Grover search with the concept of quantum protocols with classical public coins, that the quantum communication complexity for LNE(l, k) is O(√l log l + log k), where LNE(l, k) is an lk-bit total Boolean function called the list-nonequality function. The function is a generalization of the equality function and the disjoint function. The above bound gives some separation between quantum and classical communication complexity for a total function, since the classical randomized communication complexity for the same function is Θ(l + log k). As a multi-party version of the list-nonequality function, the distinctness problem is considered. The goal of this problem is to decide whether or not there are two parties that have the same inputs. The sub-optimal bound of the communication complexity of the problem is given via the model of quantum protocols with classical public coins.This paper studies the model of quantum protocols with classical public coins, and shows its application to quantum communication complexity of some functions. The paper first proves, by carefully combining quantum Grover search with the concept of quantum protocols with classical public coins, that the quantum communication complexity for LNE(l, k) is O(√l log l + log k), where LNE(l, k) is an lk-bit total Boolean function called the list-nonequality function. The function is a generalization of the equality function and the disjoint function. The above bound gives some separation between quantum and classical communication complexity for a total function, since the classical randomized communication complexity for the same function is Θ(l + log k). As a multi-party version of the list-nonequality function, the distinctness problem is considered. The goal of this problem is to decide whether or not there are two parties that have the same inputs. The sub-optimal bound of the communication complexity of the problem is given via the model of quantum protocols with classical public coins.

  • Average/Worst-Case Gap of Quantum Query Complexities (アルゴリズム(AL) Vol.2009-AL-124)

    AMBAINIS ANDRIS, IWAMA KAZUO, NAKANISHI MASAKI, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita

    情報処理学会研究報告. AL, アルゴリズム研究会報告   情報処理学会  

    発表年月: 2009年05月

    開催年月:
    2009年05月
     
     

     概要を見る

    The difference between average-case and worst-case complexities is one of the central topics in theoretical computer science, and it has been extensively studied for decades. In the quantum setting, however, only a few results are known. This paper shows a super-linear tight gap between the average-case and worst-case quantum query complexities over the families of Boolean functions defined by a natural parameter. More concretely, we consider the size of the on-set of a Boolean function f, i.e., the number of inputs for which f = 1, as the parameter, and give the tight gap over the families of N-variable Boolean functions with on-set size M for poly (N) < M < 2N /2.The difference between average-case and worst-case complexities is one of the central topics in theoretical computer science, and it has been extensively studied for decades. In the quantum setting, however, only a few results are known. This paper shows a super-linear tight gap between the average-case and worst-case quantum query complexities over the families of Boolean functions defined by a natural parameter. More concretely, we consider the size of the on-set of a Boolean function f, i.e., the number of inputs for which f = 1, as the parameter, and give the tight gap over the families of N-variable Boolean functions with on-set size M for poly (N) < M < 2N /2.

  • Flexcastに基づくマルチキャストシステムの開発とその方式設計について

    井上武, 谷誠一郎, 高橋宏和, 湊真一, 宮崎敏明, 豊島鑑

    電子情報通信学会 技術研究報告   一般社団法人電子情報通信学会  

    発表年月: 2004年06月

    開催年月:
    2004年06月
     
     

     概要を見る

    NS2004-50

  • Flexcastによるインターマルチキャスティング方式の提案と日米映像配信実験

    井上 武, 谷 誠一郎, 湊 真一, 高橋 宏和, 小田部 悟士, 宮崎 敏明

    電子情報通信学会 技術研究報告   一般社団法人電子情報通信学会  

    発表年月: 2003年06月

    開催年月:
    2003年06月
     
     

     概要を見る

    NS2003-37

  • B-7-66 リアルタイムストリーム配信における FEC 適用時の課題に関する一考察

    高橋 宏和, 谷 誠一郎, 湊 真一, 宮崎 敏明

    電子情報通信学会総合大会講演論文集   一般社団法人電子情報通信学会  

    発表年月: 2003年03月

    開催年月:
    2003年03月
     
     
  • 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (1) Flexcast と IP マルチキャストの連携方式

    谷 誠一郎, 井上 武, 湊 真一, 宮崎 敏明

    電子情報通信学会総合大会講演論文集   一般社団法人電子情報通信学会  

    発表年月: 2003年03月

    開催年月:
    2003年03月
     
     
  • 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (2) 動的アドレスマッピングによるオンデマンド IP マルチキャストトンネリング

    井上 武, 谷 誠一郎, 湊 真一, 宮崎 敏明

    電子情報通信学会総合大会講演論文集   一般社団法人電子情報通信学会  

    発表年月: 2003年03月

    開催年月:
    2003年03月
     
     
  • 自己組織化多地点配信技術 (Flexcast) を用いた自律広域マルチキャスト法 : (3) 日米間超長距離ネットワークにおける実証実験

    小田部 悟士, 谷 誠一郎, 井上 武, 高橋 宏和, 湊 真一, 宮崎 敏明

    電子情報通信学会総合大会講演論文集   一般社団法人電子情報通信学会  

    発表年月: 2003年03月

    開催年月:
    2003年03月
     
     
  • 自律広域マルチキャスト方式 Flexcast におけるソケットAPI の設計と実装

    井上武, 谷誠一郎, 湊真一, 宮崎敏明

    情報処理学会 全国大会  

    発表年月: 2003年03月

    開催年月:
    2003年03月
     
     

     概要を見る

    6K-03

  • 適応的マルチキャストによるトラヒック平滑化の効果

    太田 聡, 谷 誠一郎, 宮崎 敏明

    電子情報通信学会技術研究報告. IN, 情報ネットワーク   一般社団法人電子情報通信学会  

    発表年月: 2002年06月

    開催年月:
    2002年06月
     
     

     概要を見る

    ライヴ・ストリーミング配信はIP網の有力なサービスである.一方,このサービスの必要帯域幅は大きく,かつ変動するので,ネットワークの輻輳原因となり得る.本稿は,ライヴ・ストリーミング配信が発生するトラヒックの扱い難さがマルチキャスト技術により低減されることを計算機シミュレーションを用いて示す.アクティヴ・ネットワーク技術に基づくマルチキャスト手法の一つに着目し,同手法がトラヒックの大きさと変動を効果的に削減することを示す.また,トラヒックのバースト性を自己相似性により評価し,同手法がバースト性を平滑化することを示す.これらの結果から,同技術がライヴ・ストリーミング配信に起因する輻輳を防ぐ上で有効と結論できる.

  • SB-5-2 中継ノードでデータ形式変換可能なアクティブマルチキャストのためのジョブ割当て方法

    谷 誠一郎, 宮崎 敏明, 高橋 紀之

    電子情報通信学会ソサイエティ大会講演論文集   一般社団法人電子情報通信学会  

    発表年月: 2001年08月

    開催年月:
    2001年08月
     
     
  • IP unicast addressを用いたマルチキャスト方式の提案

    宮崎 敏明, 谷 誠一郎, 高橋 紀之

    電子情報通信学会技術研究報告. IN, 情報ネットワーク   一般社団法人電子情報通信学会  

    発表年月: 2001年05月

    開催年月:
    2001年05月
     
     

     概要を見る

    ユニキャスト通信をベース化に、複数の端末が同一サーバからのストリームデータを同時受信している場合、ネットワーク内でマルチキャスト配信木を動的に構成し、同一内容パケットが重複して同一経路を流れることを軽減する方式を提案する。本方式は、マルチキャストIPアドレスやマルチキャストのための専用機構を必要としないため、拡張性化優れ、容易に放送型ストリーム配信が実現できる。本稿では、提案方式およびその特徴を述べた後、提案方式を用いて実現したアプリケーションを紹介する。

  • アクティブネットワークを用いた動的広告付加機能付きマルチキャスト方式の提案

    谷 誠一郎, 宮崎 敏明, 高橋 紀之

    電子情報通信学会技術研究報告. IN, 情報ネットワーク   一般社団法人電子情報通信学会  

    発表年月: 2001年05月

    開催年月:
    2001年05月
     
     

     概要を見る

    近年、通信ネットワークを介してストリームデータをマルチキャスト配信するサービスが注目されている。広告付きストリームデータを配信する民放型配信サービスの場合、通信ネットワークの双方向性を利用することにより、クライアント(ユーザ)の嗜好情報を獲得し、広告付加処理にフィードバックさせることにより、高い広告効果が期待できる。本稿では、クライアント(ユーザ)の嗜好に応じて広告を付加する機能を持つ、ストリームデータのマルチキャスト配信方式を提案し、アクティブネットワーク技術を用いた提案方式の実装法を示す。

  • Competitive な網内キャッシングアルゴリズムおよびその設計手法

    谷 誠一郎

    電子情報通信学会技術研究報告. COMP, コンピュテーション   一般社団法人電子情報通信学会  

    発表年月: 2000年05月

    開催年月:
    2000年05月
     
     

     概要を見る

    ネットワークトラヒックやユーザレスポンスタイムを低減する有効な手段として, ネットワークキャッシングが注目されている。本稿では、新しくオンラインキャッシングアルゴリズムのクラスを定義し、competitive ratioの上限を与える。その結果をもとに、特定のアクセスパターンに対して有効であるがcompetitiveでないキャッシングアルゴリズムを、LRUと組み合わせることにより、competitive化する汎用的な手法を提案する。また、Size方式(大きいオブジェクトから順に削除する)とLRU(Least-Recently-Used)方式を提案手法を用いて組み合わせることにより、competitiveなアルゴリズムを構築し、その有効性を計算機実験により示す。

  • 網内資源組織化技術

    谷 誠一郎, 石原 晋也, 高原 厚, 宮崎 敏明, 松広 一良

    電子情報通信学会技術研究報告. IN, 情報ネットワーク   一般社団法人電子情報通信学会  

    発表年月: 2000年02月

    開催年月:
    2000年02月
     
     

     概要を見る

    本稿では、通信品質を考慮可能なeffortless networkの実現手法を提案する。本手法は、網内に分散した資源を抽象化し、ユーザホストのバスに直結されているかのように組織化することにより、ユーザから資源の分散性を隠蔽する。また、資源を抽象化することにより、ユーザがサービスを要求した際、そのサービスを提供する資源を、ネットワーク側が選択することが可能になる。このため、同種のサービスを提供する資源が複数あれば、ネットワークのトラフィック状況によって、ユーザからの要求が発生した時点で最適なものを選択することが可能である。また、サービス提供中であっても、より高い通信品質を実現できる資源が新たに使用可能なったときに、その資源に切替えることが可能である。

  • D-10-8 遅延故障検出のためのテストパス選択に関する一検討

    谷 誠一郎

    電子情報通信学会ソサイエティ大会講演論文集   一般社団法人電子情報通信学会  

    発表年月: 1999年08月

    開催年月:
    1999年08月
     
     
  • B-7-108 Virtual BUSにおける資源管理探索機構

    谷 誠一郎, 湊 真一, 寺元 光生

    電子情報通信学会総合大会講演論文集   一般社団法人電子情報通信学会  

    発表年月: 1999年03月

    開催年月:
    1999年03月
     
     

     概要を見る

    通信ネットワーク上の資源の分散性をユーザから隠蔽することにより、ユーザがネットワーク上に分散した資源に容易にアクセスすることを可能にする環境(Virtual BUS)を提案している。Virtual BUSにおいては、ユーザ(クライアント)が資源の正確な場所を知らなくても、利用したい資源を特徴付ける情報(属性)を与えるだけで、資源を利用することが出来る。また、属性をキーとする検索機能を提供することで、資源の動的切替え(ローミング)や資源の排他制御を可能にしている点が、従来手法に対して、一つの特徴になっている。本稿では、資源の属性や場所(ID)を管理し、所望の属性を持つ資源のIDを検索するための資源管理探索機構について、一構成案を示す。

  • 遅延故障テストにおけるテストパス選択手法の検討

    谷 誠一郎, 寺元 光生, 深澤 友雄, 松広 一良

    電子情報通信学会技術研究報告. VLD, VLSI設計技術   一般社団法人電子情報通信学会  

    発表年月: 1997年10月

    開催年月:
    1997年10月
     
     

     概要を見る

    集積回路の高速化・微細化に伴って、遅延が原因で要求される動作速度では正しく動作しない故障 (遅延故障) が問題となる. このため、遅延故障テストの重要性が高まっている. 遅延故障テストを行う際に問題となるのは、テストパスの選択手法である. 本研究では、遅延の計算誤差やプロセス変動による、設計上の遅延と実遅延の誤差を考慮した、テストパス選択手法を提案する. また、選択すべきテストパス数と、遅延誤差及びテストによって保証すべき動作速度との関係について検討を行う.

  • Tutte 多項式の計算とBDD

    関根 京子, 今井 浩, 谷 誠一郎

    電子情報通信学会技術研究報告. COMP, コンピュテーション   一般社団法人電子情報通信学会  

    発表年月: 1995年07月

    開催年月:
    1995年07月
     
     

     概要を見る

    グラフのTutte多項式を計算する問題は、グラフ理論のみならず統計物理学や結び目の理論等とも関連をもち、最近注目を集めている。この問題は#P-困難であり、指数オーダーの時間を要するアルゴリズムしか知られていない。本稿では計算の途中に多くの2-同型マイナーが現れることを利用した新しいアルゴリズムを示す。また組合せ論のBell数およびCatalan数を用いてアルゴリズムの計算量の解析をおこなう。このアルゴリズムにより、高々頂点数14かつ辺の数が91であるような任意のグラフ、さらに平面グラフにおいては頂点数144かつ辺の数が264の12×12格子グラフのTutte多項式を標準的なワークステーションにおいて約1時間で計算することができる。

  • 2分決定グラフ、ガウスの消去法、グラフ理論

    今井 浩, 谷 誠一郎

    情報処理学会研究報告. AL, アルゴリズム研究会報告   一般社団法人情報処理学会  

    発表年月: 1994年09月

    開催年月:
    1994年09月
     
     

     概要を見る

    2分決定グラフは,論理関数を効率よく表現することができ,広く用いられている.本論文では,グラフや計算幾何の問題の解を特性関数を用いて論理関数で表してその論理関数を2分決定グラフで表現するとき,その2分決定グラフの大きさを小さくする問題が,グラフ理論で確立されているグラフとガウスの消去法の関連を用いることにより,高速かつ高性能で解けることを示す.2分決定グラフで表現するグラフの性質としては,全域木,マッチング,クリーク,安定集合を考え,その2分決定グラフをよい変数順序を選んで最小化するために,平面分離定理などのグラフ理論の成果を適用する.これにより,たとえば,任意のn点単純平面グラフに対して,その全域木を表す0(n)変数の論理関数は0(4^<<√<n>>>)の大きさの2分決定木で表現することができ,その安定集合を表すn変数の論理関数を0(n2^<<√<n>>>)の大きさの2分決定木で表現することができることを示す.また,OBDDパッケージを用いてこれらの論理関数を構成した計算機実験の結果についても述べる.本論文で扱う論理関数はグラフに関連したもので特殊なクラスではあるが,一般の論理関数を表す2分決定グラフに関しても有用な知見が得られる.

▼全件表示

共同研究・競争的資金等の研究課題

  • 量子計算資源量に制約がある量子計算のための理論基盤

    日本学術振興会  科学研究費助成事業 基盤研究(A)

    研究期間:

    2022年04月
    -
    2027年03月
     

    谷 誠一郎, 西村 治道, 森 立平, 森前智行

  • 量子アルゴリズムの理論と実装を接続する革新的基盤の創出

    日本学術振興会  科学研究費助成事業 学術変革領域研究(A)

    研究期間:

    2020年11月
    -
    2025年03月
     

    山下 茂, 山本 直樹, ルガル フランソワ, 森 立平, 谷 誠一郎, 西村 治道

     概要を見る

    万能量子計算モデルに関する研究として, SWAPテストの,量子分散計算における検証に応用可能な良い性質を見つけ,その性質を利用して,一方向量子通信計算量プロトコルから 量子分散計算における検証プロトコルへ変換するための汎用的手法を開発した.その汎用的手法をデータの等価性判定問題に適用することによって,等価性判定問題に対する量子分散検証プロトコルを構成し,古典分散検証プロトコルより指数的に短い証拠の長さで同問題を検証できることを明らかにした.別の研究として,QRAMと呼ばれる量子メモリを必要とするグラフの彩色数を計算する O(1.914^n) 時間の量子アルゴリズムを示した.
    能力が限定された量子計算モデルに関する研究に関して,量子対話系の計算モデルにおいて,より制限された量子計算では基底状態の生成が困難である証拠を得た.具体的には,成功確率が指数的に小さくても許される量子対話証明を用いて基底状態の生成を行う際に,数え上げ階層が崩壊しないという仮定のもとで,検証者が得る証明を古典状態に制限することはできないことを示した.
    量子分散計算に関して,k-clique問題を解く高速な古典分散アルゴリズムの開発を行い,量子通信による更なら高速化の可能性について調査した.また,k-clique問題を解く実用的なアプローチを提案し,NISQデバイス上での実装を検討した.
    量子回路設計に関して,任意の量子回路をlattice surgeryにマッピングする際に,latticeの回転操作を利用することで,論理量子ビットの充填率を.既存手法と比べて平均して45.9%削減できる手法を考案した.
    誤り耐性がない量子計算機を利用するスキームとして,量子リザバー計算機による時系列データ処理法を考案した.IBMQをリザバー計算機として実現し,ベンチマーク問題において古典線形回帰よりも良い時系列分類が可能であることを実証した.

  • 量子力学からの計算限界解明へのアプローチ

    日本学術振興会  科学研究費助成事業 新学術領域研究(研究領域提案型)

    研究期間:

    2012年06月
    -
    2017年03月
     

    山下 茂, 河内 亮周, 中西 正樹, ルガル フランソワ, 西村 治道, 小林 弘忠, 谷 誠一郎, 根本 香絵, 村尾 美緒, 伊藤 剛志

     概要を見る

    量子力学特有の現象を利用した計算および通信の次世代の方式として、量子計算・量子通信と呼ばれる方式が提案され、現在までに多くの研究が行われてきている。この計算・通信方式は、現在使われている方式に比べてある状況では圧倒的に能力が高い可能性があることがわかっている。しかし、量子計算・量子通信の能力について完全には明らかになっていない。そのため、本研究課題では、量子計算および量子通信について計算量的なアプローチで、今まで知られていなかった能力に関しての解析を行い、新たな知見を得た。また、量子計算・量子通信の能力を解析するテクニックを用いて現在の計算方式の能力を解析する新たな研究成果も得た。

  • 分散環境における量子計算量能力のネットワーク形状に着目した解析

    日本学術振興会  科学研究費助成事業 若手研究(B)

    研究期間:

    2007年
    -
    2009年
     

    谷 誠一郎

     概要を見る

    量子計算能力を持つ通信ノードを量子通信路によって相互に接続することにより構成される量子ネットワーク上において,分散している入力に依存する関数計算(分散計算)を行うために要する量子通信量を検討した.その結果,分散計算に要する量子通信量は,計算すべき関数とネットワークの形状を規定するパラメータで特徴づけられることを明らかにした.さらに,具体的な問題に対して,本結果を応用することにより,準最適な量子通信量が得られた.

Misc

  • Dilemma between Quantum Speedup and Computational Reliability—Overcoming Errors with Efficient Verification Methods for Quantum Computing

    Yuki Takeuchi, Seiichiro Tani

    NTT Technical Review   21 ( 10 ) 26 - 29  2023年10月

     概要を見る

    Quantum computers are expected to solve several problems faster than any classical computer. However, they may sometimes output incorrect answers because they are prone to errors. Therefore, to develop reliable quantum computers, it is essential to develop methods of verifying whether the outputs of quantum computers are correct. In this article, we introduce our recent research results on our verification methods.

    DOI

  • Extracting Quantum Power by Using Algorithms and Their Verification

    Seiichiro Tani, Seiseki Akibue, Yuki Takeuchi

    NTT Technical Review   21 ( 6 ) 43 - 47  2023年06月

     概要を見る

    Quantum computers are expected to increase computational speed compared with current and future computers that work in accordance with the conventional computational principle and to revolutionize information processing. Such an increase in speed is achieved using quantum algorithms that extract computational power from quantum-computer hardware. This article briefly introduces our recent results on quantum algorithms, quantum-circuit optimization to support their efficient implementation, and quantum-circuit verification necessary for their reliable execution.

    DOI

  • 量子技術イノベーションに向けた取り組み 量子コンピュータの能力を引き出すアルゴリズムとその検証技術

    谷誠一郎, 秋笛清石, 竹内勇貴

    NTT技術ジャーナル   35 ( 4 ) 29 - 32  2023年04月  [招待有り]   [ 国内誌 ]

    担当区分:筆頭著者, 責任著者

    記事・総説・解説・論説等(商業誌、新聞、ウェブメディア)  

    J-GLOBAL

  • 多様な知と技術が彩るだれもがどこでも輝ける未来 量子コンピュータにおける計算高速性と信頼性のジレンマ-計算結果の正しさの効率的な検証技術による量子エラーの克服

    竹内勇貴, 谷誠一郎

    NTT技術ジャーナル   35 ( 8 )  2023年

    J-GLOBAL

  • NISQ計算の分割統治による検証

    竹内勇貴, 高橋康博, 森前智行, 谷誠一郎

    情報処理学会全国大会講演論文集   85th ( 1 )  2023年  [査読有り]   [ 国際誌 ]

    DOI J-GLOBAL

  • 新原理コンピュータへの取り組み 量子コンピュータの実装技術の課題克服に向けた理論面からの取り組み

    秋笛清石, 竹内勇貴, 高橋康博, 加藤豪, 谷誠一郎

    NTT技術ジャーナル   33 ( 3 )  2021年03月  [招待有り]   [ 国内誌 ]

    担当区分:最終著者, 責任著者

    記事・総説・解説・論説等(商業誌、新聞、ウェブメディア)  

    J-GLOBAL

  • 量子アルゴリズム概観

    谷 誠一郎

    電子情報通信学会 通信ソサイエティマガジン   14 ( 2 ) 102 - 112  2020年09月  [招待有り]   [ 国内誌 ]

    担当区分:責任著者

    記事・総説・解説・論説等(学術雑誌)  

     概要を見る

    量子コンピュータは,量子力学の原理を用いて計算を行うコンピュータであり,現在のコンピュータを超える計算能力を発揮することが期待されている.そのためには,量子コンピュータのハードウェアを効果的に使って計算を行うアルゴリズム(量子アルゴリズム)が必要となる.本稿では,これまで行われてきた量子アルゴリズム研究を概観し,課題と展望について議論する

    DOI CiNii

  • 高速量子アルゴリズムの開発

    谷 誠一郎, 高橋 康博

    IEICE FUNDAMENTALS REVIEW   14 ( 1 ) 15 - 27  2020年07月  [招待有り]   [ 国内誌 ]

    担当区分:筆頭著者

     概要を見る

    量子コンピュータは現在のコンピュータにおける不可能を可能にする高速コンピュータとして大きな期待を集めている.この期待の実現には,新しいハードウェア技術とともに,ハードウェアの能力を引き出す新しいアルゴリズム技術が不可欠である.本稿では,このような高速量子アルゴリズムの開発に焦点を当て,量子コンピュータ単体による計算や通信が可能な複数の量子コンピュータを利用する計算のために開発されてきた高速量子アルゴリズムの歴史を振り返るとともに,我々の成果について,その原点となる発想を中心に紹介する.

    DOI CiNii

  • A period without direction is a time for improving one's basic research abilities-better to change your perspective than follow the crowd

    Seiichiro Tani

    NTT Technical Review   16 ( 2 )  2018年02月

    書評論文,書評,文献紹介等  

     概要を見る

    Research toward the development of a practical quantum computer began more than 30 years ago in the 1980s, and it is now entering a new phase. The Ministry of Education, Culture, Sports, Science and Technology in Japan recognizes the significance of this development and has included 3.2 billion yen in its budget request as a development fund for photonics-quantum technology. Senior Distinguished Researcher Seiichiro Tani of NTT Communication Science Laboratories has had many world-first achievements in this field. The quantum computer is attracting attention as a driver of future trends, so we asked him to tell us about the current state of quantum computer research and some research achievements. We also asked him his views on how a researcher should approach the work of research.

  • 素因数分解だけではない量子計算の魅力 : 量子探索技術の可能性を探る—特集 コミュニケーション科学の新展開

    谷 誠一郎

    NTT技術ジャーナル / 日本電信電話株式会社 編   26 ( 9 ) 37 - 41  2014年09月  [招待有り]   [ 国内誌 ]

    担当区分:責任著者

    記事・総説・解説・論説等(商業誌、新聞、ウェブメディア)  

    CiNii

  • EVENT REPORTS 「NTTコミュニケーション科学基礎研究所オープンハウス2012」開催報告

    笠原 要, 谷 誠一郎, 木下 慶介

    NTT技術ジャーナル / 日本電信電話株式会社 編   24 ( 9 ) 82 - 84  2012年09月

    CiNii

  • Special Section on Frontier of Quantum Computing FOREWORD

    Seiichiro Tani

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES   E92A ( 5 ) 1253 - 1253  2009年05月

    担当区分:責任著者

    その他  

  • FOREWORD

    TANI Seiichiro

    IEICE transactions on fundamentals of electronics, communications and computer sciences   92 ( 5 ) 1253 - 1253  2009年05月

    担当区分:責任著者

    DOI CiNii

  • 量子コンピュータと量子計算 : 4.情報・物理双方から見た量子探索アルゴリズムの基礎

    加藤豪, 谷 誠一郎

    情報処理   47 ( 12 ) 1329 - 1334  2006年12月  [招待有り]

    担当区分:最終著者

     概要を見る

    量子計算アルゴリズムの中で,Shorの因数分解アルゴリズムと並び,最も有名なものは,Groverの探索アルゴリズムであろう.最良の古典アルゴリズムとの性能比は,因数分解アルゴリズムのそれに及ばないが,探索アルゴリズムが扱っている問題は非常に一般性があり,さまざまな応用が期待されている.本稿では,Groverの探索アルゴリズムと,その主な発展形について解脱する.

    CiNii

  • グループトピックス 「NTTコミュニケーション科学基礎研究所オープンハウス2005」開催報告

    須山 敬之, 高田 敏弘, 谷 誠一郎

    NTT技術ジャーナル / 日本電信電話株式会社 編   17 ( 11 ) 56 - 58  2005年11月

    CiNii

  • 特集「量子計算と量子情報」の編集にあたって

    谷 誠一郎

    情報処理学会論文誌   46 ( 10 ) 2383 - 2383  2005年10月

    CiNii

  • 『情報学のための離散数学』, 茨木俊秀(著), 昭晃堂, 2004-03, A5判, 定価(本体3,450円+税)

    谷 誠一郎

    電子情報通信学会誌   87 ( 11 ) 997 - 997  2004年11月

    CiNii

  • Global Multi-Point Streaming Experiments Based on Flexcast Protocol

    Seiichiro Tani, Takeru Inoue, Shin-ichi Minato, Hirokazu Takahashi, Satoshi Kotabe, Toshiaki Miyazaki

    NTT Technical Review   1 ( 5 ) 24 - 30  2003年08月

    記事・総説・解説・論説等(大学・研究所紀要)  

  • Flexcast:自己組織化多地点配信技術

    谷 誠一郎, 宮崎 敏明, 高橋 紀之

    NTT R & D   52 ( 3 ) 213 - 222  2003年03月

    CiNii

  • Active network technology: Towards the adaptive network infrastructure

    T Miyazaki, N Takahashi, T Murooka, S Tani

    NTT REVIEW   14 ( 2 ) 99 - 107  2002年03月  [査読有り]

     概要を見る

    It is very important to realize an adaptive network that can dynamically adapt itself to users' needs and data traffic. We are developing the Active Network (AN) environment as a basic mechanism to realize such a network. AN is a network technology that enables us to introduce new services easily by attaching programs to the packets and evaluating the programs at each router. After introducing our AN environment, this article describes the active router, the most important part of the AN. In addition, a streaming multicast application that uses the AN is presented.

▼全件表示

産業財産権

▼全件表示

 

現在担当している科目

▼全件表示

 

他学部・他研究科等兼任情報

  • 教育・総合科学学術院   大学院教育学研究科