Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication
スポンサーリンク
概要
- 論文の詳細を見る
In this paper we study quantum nondeterminism in multiparty communication. There are three (possibly) different types of nondeterminism in quantum computation: i) strong, ii) weak with classical proofs, and iii) weak with quantum proofs. Here we focus on the first one. A strong quantum nondeterministic protocol accepts a correct input with positive probability and rejects an incorrect input with probability 1. In this work we relate strong quantum nondeterministic multiparty communication complexity to the rank of the communication tensor in the Number-On-Forehead and Number-In-Hand models. In particular, by extending the definition proposed by de Wolf to nondeterministic tensor-rank (nrank), we show that for any boolean function f when there is no prior shared entanglement between the players, 1) in the Number-On-Forehead model the cost is upper-bounded by the logarithm of nrank(f); 2) in the Number-In-Hand model the cost is lower-bounded by the logarithm of nrank(f). Furthermore, we show that when the number of players is o(log log n), we have $NQP\nsubseteq BQP$ for Number-On-Forehead communication.
著者
-
NAKASHIMA Yasuhiko
Graduate School of Information Science, Nara Institute of Science and Technology
-
Nakashima Yasuhiko
Graduate School Of Information Science Naist
-
Yamashita Shigeru
Department Of Biochemistry Toho University School Of Medicine
-
Nakanishi Masaki
Faculty Of Education Art And Science Yamagata University
-
VILLAGRA Marcos
Graduate School of Information Science, Nara Institute of Science and Technology
関連論文
- An Instruction Mapping Scheme for FU Array Accelerator
- Inhibition of apoptosis by ascorbic and dehydroascorbic acids in Xenopus egg extracts
- An EDP Study on the Optimal Pipeline Depth for Pipeline Stage Unification Adoption
- Dynamic Control Mechanisms for Pipeline Stage Unification Based on Program Phase Detection
- Dynamic Control Mechanisms for Pipeline Stage Unification Based on Program Phase Detection(集積回路技術とアーキテクチャ技術の協調・融合へ向けた,プロセッサ,並列処理,システムLSIアーキテクチャ及び一般)
- ReVolver/C40 : A Scalable Parallel Computer for Volume Rendering-Design and Implementation-(Development of Advanced Computer Systems)
- Parallel Cloth Simulation with Adaptive Mesh Refinement and Coarsening Using OpenMP on Fujitsu HPC2500(Parallel Processing Applications)
- An approach towards fast simulation of virtual cloth with adaptive mesh refinement and coarsening on Fujitsu HPC2500
- Priority Enhanced Stride Scheduling
- Effects of GOISHICHA Extracts on Fatty Acid Compositions of Brain and Liver Lipid in Rats
- Effects of Extracts from GOISHICHA on Serum and Liver Lipid Concentrations in Rats〔邦文〕
- Intrahepatic Pseudoaneurysm After Surgical Hemostasis for a Delayed Hemorrhage Due to Blunt Liver Injury : Report of a Case
- Critical Current and Pinning Effect in Type I Superconducting Lead Foils with Thickness Modulation
- Critical Current Measurements in Type I Superconducting Lead Foils by Shadow Electron Microscopy
- Observation of the Intermedeate State in Superconducting Lead Films by Shadow Electron Microscopy
- An efficient middle-level framework for quantum circuit simulation on multiple simulator platforms (コンピュータシステム)
- Polarizing and Electron Microscope Studies of Structural Phase Transitions in CsVF_4
- Quantum Walks on the Line with Phase Parameters
- Mass Spectrometric Study of Photofragment Free Radicals in the Photolyses of a Few Molecules
- RazorProtector: Maintaining Razor DVS Efficiency in Large IR-Drop Zones by an Adaptive Redundant Data-Path
- Selective Check of Data-Path for Effective Fault Tolerance
- Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication
- Induction of Giant Endothelial Cells in Culture by K-252a, a Protein Kinase Inhibitor.
- A Study of the Primary Processes in Photochemical Reactions by Photofragment Mass Spectrometry
- Chromosome Condensation in HeLa Cells Induced by β-Glycerophosphate
- Mass spectrometric study of the primary processes in photochemical reactions. III. Primary steps in simple ketone photolysis and mass spectrum of acetyl radical.
- Inhibitory Effects of Caffeine on Contraction of Depolarized Smooth Muscle.