Multi-Party Quantum Communication Complexity with Routed Messages

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• （社）電子情報通信学会の論文
• 2009-02-01

著者

• TANI SEIICHIRO

  NTT Communication Science Laboratories, NTT Corporation

• YAMASHITA SHIGERU

  Graduate School of Information Science, Nara Institute of Science and Technology

• Tani Seiichiro

  Ntt Communication Science Laboratories Ntt Corporation

• Nakanishi Masaki

  Graduate School Of Information Science Nara Institute Of Science And Technology

• Yamashita Shigeru

  Graduate School Of Information Science Nara Institute Of Science And Technology

関連論文

• Average/Worst-Case Gap of Quantum Query Complexities
• General Bounds for Quantum Biased Oracles (特集:量子計算と量子情報)
• Bit Length Optimization of Fractional Part on Floating to Fixed Point Conversion for High-Level Synthesis(Logic and High Synthesis)(VLSI Design and CAD Algorithms)
• Robust Quantum Algorithms Computing OR with ε-Biased Oracles(Quantum Computing,Foundations of Computer Science)
• Bit-Length Optimization Method for High-Level Synthesis Based on Non-linear Programming Technique(System Level Design,VLSI Design and CAD Algorithms)
• FOREWORD
• On the Power of Non-deterministic Quantum Finite Automata(Special Issue on Selected Papers from LA Symposium)
• Multi-Party Quantum Communication Complexity with Routed Messages
• SPFD-Based Flexible Transformation of LUT-Based FPGA Circuits(VLSI Design Technology and CAD)
• General Bounds for Quantum Biased Oracles

スポンサーリンク