論文の概要: Exact quantum query complexity of computing Hamming weight modulo powers
of two and three
- arxiv url: http://arxiv.org/abs/2112.14682v1
- Date: Wed, 29 Dec 2021 17:57:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-02 23:16:44.199373
- Title: Exact quantum query complexity of computing Hamming weight modulo powers
of two and three
- Title（参考訳）: 2と3の重みモジュロパワーを阻害する計算の厳密な量子クエリー複雑性
- Authors: Arjan Cornelissen and Nikhil S. Mande and Maris Ozols and Ronald de
Wolf
- Abstract要約: この問題の正確な量子クエリ複雑性は、$leftlceil n (1 − 1/m) rightil$であることを示す。
上界は、主成分がよく知られた1-クエリ量子アルゴリズムである反復クエリアルゴリズムによって構成される。
- 参考スコア（独自算出の注目度）: 2.1349209400003932
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of computing the Hamming weight of an $n$-bit string
modulo $m$, for any positive integer $m \leq n$ whose only prime factors are 2
and 3. We show that the exact quantum query complexity of this problem is
$\left\lceil n(1 - 1/m) \right\rceil$. The upper bound is via an iterative
query algorithm whose core components are the well-known 1-query quantum
algorithm (essentially due to Deutsch) to compute the Hamming weight a 2-bit
string mod 2 (i.e., the parity of the input bits), and a new 2-query quantum
algorithm to compute the Hamming weight of a 3-bit string mod 3.
We show a matching lower bound (in fact for arbitrary moduli $m$) via a
variant of the polynomial method [de Wolf, SIAM J. Comput., 32(3), 2003]. This
bound is for the weaker task of deciding whether or not a given $n$-bit input
has Hamming weight 0 modulo $m$, and it holds even in the stronger
non-deterministic quantum query model where an algorithm must have positive
acceptance probability iff its input evaluates to 1. For $m>2$ our lower bound
exceeds $n/2$, beating the best lower bound provable using the general
polynomial method [Theorem 4.3, Beals et al., J. ACM 48(4), 2001].
- Abstract（参考訳）: 素因子が 2 と 3 のみである任意の正の整数 $m \leq n$ に対して、$n$-bit string modulo $m$ のハミング重みを計算する問題を研究する。
この問題の正確な量子クエリの複雑性は$\left\lceil n(1 - 1/m) \right\rceil$である。
上界は、2ビットの文字列 mod2(すなわち入力ビットのパリティ)のハミング重みを計算するためによく知られた1-query量子アルゴリズム(基本的にはdeutschによる)の中核成分である反復的クエリアルゴリズムと、3-ビットの文字列 mod 3のハミング重みを計算する新しい2-query量子アルゴリズムである。
多項式法の変種 (de Wolf, SIAM J. Comput., 32(3), 2003) を通して、一致する下界(実際には任意のモジュライ$m$)を示す。
このバウンドは、与えられた$n$-bit入力が0 modulo $m$という重みを持つかどうかを判断する弱いタスクであり、アルゴリズムがその入力を1に評価する正の受け入れ確率を持つ必要がある強い非決定論的量子クエリモデルでさえ保持する。
m>2$ の場合、我々の下界は$n/2$ を超え、一般多項式法(英語版)(Theorem 4.3, Beals et al., J. ACM 48(4), 2001)を用いて証明できる最高の下界を破る。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Logarithmic-Depth Quantum Circuits for Hamming Weight Projections [3.481985817302898]
入力純状態上でのコヒーレントハミング重みの射影測定を実現する量子アルゴリズムを提案する。
我々は、対応する量子回路の深さ幅のトレードオフを分析し、より多くの制御量子ビットのコストで回路の深さの低減を可能にする。
論文 参考訳（メタデータ） (2024-04-10T16:35:36Z) - A simple lower bound for the complexity of estimating partition functions on a quantum computer [0.20718016474717196]
分割関数 $mathsfZ(beta)=sum_xinchi e-beta H(x)$ をハミルトニアン$H(x)$ で特徴づけられるギブス分布に対して推定する複雑性について検討する。
我々は、ギブス状態のコヒーレントな符号化を通して反射に依存することにより、この問題を解く量子アルゴリズムの単純で自然な下界を提供する。
論文 参考訳（メタデータ） (2024-04-03T02:38:49Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - 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) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Pauli String Partitioning Algorithm with the Ising Model for
Simultaneous Measurement [0.0]
本研究では,パウリ弦を1つの量子回路で同時に測定可能な部分群に分割する効率的なアルゴリズムを提案する。
我々の分割アルゴリズムは、量子化学のための変分量子固有解法における測定総数を劇的に削減する。
論文 参考訳（メタデータ） (2022-05-09T01:49:21Z) - A quantum algorithm for computing the Carmichael function [0.0]
量子コンピュータは、多くの数理論問題を効率的に解くことができる。
本稿では,任意の整数$N$に対して,所望の 1 に近い確率でカーマイケル関数を計算するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-11-03T19:30:27Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。