Robust Quantum Algorithms Computing OR with ε-Biased Oracles(Quantum Computing,<Special Section>Foundations of Computer Science)
スポンサーリンク
概要
- 論文の詳細を見る
This paper considers the quantum query complexity of ε-biased oracles that return the correct value with probability only 1/2+ε. In particular, we show a quantum algorithm to compute N-bit OR functions with O(√<N>/ε) queries to ε-biased oracles. This improves the known upper bound of O(√<N>/ε^2) and matches the known lower bound; we answer the conjecture raised by the paper [1] affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of ε. This contrasts with the corresponding classical situation, where it is almost hopeless to construct a bounded error algorithm without knowing the value of ε.
- 社団法人電子情報通信学会の論文
- 2007-02-01
著者
-
WATANABE Katsumasa
Graduate School of Information Science, Nara Institute of Science and Technology
-
Suzuki Tomoya
Graduate School Of Science Tokyo University Of Science
-
NAKANISHI MASAKI
Graduate School of Information Science, NAIST
-
YAMASHITA SHIGERU
Graduate School of Information Science, Nara Institute of Science and Technology
-
Watanabe Katsumasa
Graduate School Of Information Science Nara Institute Of Science And Technology
-
Suzuki Tomoya
Graduate School Of Information Science Nara Institute Of Science And Technology
-
Yamashita Shigeru
Nara Inst. Sci. And Technol. Ikoma‐shi Jpn
-
Nakanishi Masaki
Graduate School Of Information Science Nara Institute Of Science And Technology
-
Nakanishi Masaki
Nara Inst. Sci. And Technol. Ikoma‐shi Jpn
-
NAKANISHI Masaki
Yamagata University
-
YAMASHITA Shigeru
Ritsumeikan University
-
Yamashita Shigeru
Graduate School Of Information Science Nara Institute Of Science And Technology
-
Suzuki Tomoya
Graduate School of Doshisha University
関連論文
- 若手からのメッセｰジ
- Exact Minimization of Free BDDs and Its Application to Pass-Transistor Logic Optimization (Special Section on VLSI Design and CAD Algorithms)
- Hardware Synthesis from C Programs with Estimation of Bit Length of Variables (Special Section on VLSI Design and CAD Algorithms)
- CGとセンサによるロボットのCG頭部実現方法(ヒューマンインタフェース基礎)
- サロゲート法おける窓関数の効果(非線形回路とシステム,及び一般)
- サロゲート法おける窓関数の効果(非線形回路とシステム,及び一般)
- A-2-25 Surrogate Test for Chaos Game Representation
- Average/Worst-Case Gap of Quantum Query Complexities
- General Bounds for Quantum Biased Oracles (特集:量子計算と量子情報)
- 経済現象って予測できるの?(5. 若手からのメッセージ)(未来への手紙)
- 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)
- Look Up Table Compaction Based on Folding of Logic Functions(Special Section on 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)
- Quantum Biased Oracles (特集:量子計算と量子情報)
- DDMF : An Efficient Decision Diagram Structure for Design Verification of Quantum Circuits under a Practical Restriction
- An Efficient and Effective Algorithm for Online Task Placement with I/O Communications in Partially Reconfigurable FPGAs(System Level Design,VLSI Design and CAD Algorithms)
- Quantum versus Classical Pushdown Automata in Exact Computation (特集:量子計算と量子情報)
- 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
- An efficient middle-level framework for quantum circuit simulation on multiple simulator platforms (コンピュータシステム)
- SPFD-Based Flexible Transformation of LUT-Based FPGA Circuits(VLSI Design Technology and CAD)
- Automatic Generation of Java-Based, Database-Independent Query API
- Automatic Generation of Java-Based, Database-Independent Query API
- Secure Processor Architecture for High-Speed Verification of Memory Integrity
- Automata with Quantum and Classical Resources (特集:量子計算と量子情報)
- Quantum Walks on the Line with Phase Parameters
- Symbolic Discord Computation for Efficient Analysis of Message Sequence Charts
- Laser-based road recognition for a smart electric wheelchair
- General Bounds for Quantum Biased Oracles
- Clique-Based Architectural Synthesis of Flow-Based Microfluidic Biochips
- Quantum Biased Oracles
- Quantum versus Classical Pushdown Automata in Exact Computation
- Quantum Biased Oracles