論文の概要: Tolerant Quantum Junta Testing

• arxiv url: http://arxiv.org/abs/2411.02244v1
• Date: Mon, 04 Nov 2024 16:34:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-05 14:38:28.094496
• Title: Tolerant Quantum Junta Testing
• Title（参考訳）: Tolerant Quantum Junta Testing
• Authors: Zhaoyang Chen, Lvzhou Li, Jingquan Luo,
• Abstract要約: 耐久ジャンタテストは標準バージョンよりも一般的で難しい。 我々は、ユニタリが$epsilon$-juntaか、または任意の量子$k$-juntaから$epsilon$-farかを決定する最初のアルゴリズムを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Junta testing for Boolean functions has sparked a long line of work over recent decades in theoretical computer science, and recently has also been studied for unitary operators in quantum computing. Tolerant junta testing is more general and challenging than the standard version. While optimal tolerant junta testers have been obtained for Boolean functions, there has been no knowledge about tolerant junta testers for unitary operators, which was thus left as an open problem in [Chen, Nadimpalli, and Yuen, SODA2023]. In this paper, we settle this problem by presenting the first algorithm to decide whether a unitary is $\epsilon_1$-close to some quantum $k$-junta or is $\epsilon_2$-far from any quantum $k$-junta, where an $n$-qubit unitary $U$ is called a quantum $k$-junta if it only non-trivially acts on just $k$ of the $n$ qubits. More specifically, we present a tolerant tester with $\epsilon_1 = \frac{\sqrt{\rho}}{8} \epsilon$, $\epsilon_2 = \epsilon$, and $\rho \in (0,1)$, and the query complexity is $O\left(\frac{k \log k}{\epsilon^2 \rho (1-\rho)^k}\right)$, which demonstrates a trade-off between the amount of tolerance and the query complexity. Note that our algorithm is non-adaptive which is preferred over its adaptive counterparts, due to its simpler as well as highly parallelizable nature. At the same time, our algorithm does not need access to $U^\dagger$, whereas this is usually required in the literature.
• Abstract（参考訳）: ブール関数のユンタテストは、理論計算機科学におけるここ数十年の長い研究のきっかけとなり、近年は量子コンピューティングのユニタリ演算子についても研究されている。 耐久ジャンタテストは標準バージョンよりも一般的で難しい。 ブール関数に対して最適寛容順多テスタが得られたが、ユニタリ作用素に対する寛容順多テスタに関する知識は存在せず、[Chen, Nadimpalli, and Yuen, SODA2023] では未解決の問題として残されている。 本稿では、この問題を、ある量子$k$-juntaに対してユニタリが$\epsilon_1$-closeであるかどうか、または任意の量子$k$-juntaから$\epsilon_2$-farであるかどうかを判定する最初のアルゴリズムを提示することにより解決する。 具体的には、$\epsilon_1 = \frac{\sqrt{\rho}}{8} \epsilon$, $\epsilon_2 = \epsilon$, and $\rho \in (0,1)$で、クエリ複雑性は$O\left(\frac{k \log k}{\epsilon^2 \rho (1-\rho)^k}\right)$である。 このアルゴリズムは適応的でないが、より単純で並列化しやすい性質のため適応的でない。 同時に、我々のアルゴリズムは$U^\dagger$にアクセスする必要はない。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
  確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。 我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。 クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-25T15:32:37Z)
• On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
  我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。 我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
  論文  参考訳（メタデータ） (2023-03-20T08:17:32Z)
• Unitarity estimation for quantum channels [7.323367190336826]
  ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。 我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。 アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
  論文  参考訳（メタデータ） (2022-12-19T09:36:33Z)
• Testing and Learning Quantum Juntas Nearly Optimally [3.030969076856776]
  量子量$k$-juntasの検証と学習の問題を考察する。 a)$widetildeO(sqrtk)$-query量子アルゴリズムを与え、量子$k$-juntaと量子$k$-juntaの「遠い」ユニタリ行列を区別することができる。 我々は、量子$k$-juntasのテストと量子$k$-juntasの学習のための上限を、ほぼ一致する$Omega(sqrtk)$と$Omega(frac)$で補完する。
  論文  参考訳（メタデータ） (2022-07-13T00:11:14Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Testing Boolean Functions Properties [1.5924410290166868]
  関数のプロパティテストの分野での目標は、与えられたブラックボックスのブール関数が特定のプロパティを持っているか、あるいはそのプロパティが持たない$varepsilon$-farであるかどうかを決定することである。 ここでは、Deutsch-Jozsaアルゴリズムを用いてブール関数(同一性、相関、平衡性)のテストを行ういくつかの性質について検討する。
  論文  参考訳（メタデータ） (2021-09-14T15:27:38Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。