論文の概要: Quantum majority vote
- arxiv url: http://arxiv.org/abs/2211.11729v1
- Date: Mon, 21 Nov 2022 18:47:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-17 23:16:27.353937
- Title: Quantum majority vote
- Title（参考訳）: 量子多数決
- Authors: Harry Buhrman and Noah Linden and Laura Man\v{c}inska and Ashley
Montanaro and Maris Ozols
- Abstract要約: 多数決は、コンピュータ科学などで広く使われている正しい結果を増幅するための基本的な方法である。
この問題に対する最適アルゴリズムは,1/2 + Theta (1/sqrtn)$の最悪のケース忠実度を実現する。
入力キュービットの少なくとも2/3ドルが多数にあるという約束のもと、その忠実度は1- Theta (1/n)$に増加し、n$が増加するにつれて1ドルに近づいた。
- 参考スコア（独自算出の注目度）: 1.43494686131174
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Majority vote is a basic method for amplifying correct outcomes that is
widely used in computer science and beyond. While it can amplify the
correctness of a quantum device with classical output, the analogous procedure
for quantum output is not known. We introduce quantum majority vote as the
following task: given a product state $|\psi_1\rangle \otimes \dots \otimes
|\psi_n\rangle$ where each qubit is in one of two orthogonal states
$|\psi\rangle$ or $|\psi^\perp\rangle$, output the majority state. We show that
an optimal algorithm for this problem achieves worst-case fidelity of $1/2 +
\Theta(1/\sqrt{n})$. Under the promise that at least $2/3$ of the input qubits
are in the majority state, the fidelity increases to $1 - \Theta(1/n)$ and
approaches $1$ as $n$ increases.
We also consider the more general problem of computing any symmetric and
equivariant Boolean function $f: \{0,1\}^n \to \{0,1\}$ in an unknown quantum
basis, and show that a generalization of our quantum majority vote algorithm is
optimal for this task. The optimal parameters for the generalized algorithm and
its worst-case fidelity can be determined by a simple linear program of size
$O(n)$. The time complexity of the algorithm is $O(n^4 \log n)$ where $n$ is
the number of input qubits.
- Abstract（参考訳）: 多数決は、コンピュータ科学などで広く使われている正しい結果を増幅するための基本的な方法である。
量子デバイスの正しさを古典的な出力で増幅することができるが、量子出力の類似の手順は知られていない。
積状態 $|\psi_1\rangle \otimes \dots \otimes |\psi_n\rangle$ が与えられたとき、各キュービットは2つの直交状態 $|\psi\rangle$ または $|\psi^\perp\rangle$ のどちらかに属する。
この問題の最適アルゴリズムは、1/2 + \theta(1/\sqrt{n})$ の最悪の場合の忠実性を達成する。
入力キュービットの少なくとも2/3ドルが多数にあるという約束のもと、その忠実度は1 - \Theta(1/n)$に増加し、n$が増加するにつれて1ドルに近づく。
また、対称で同変のブール関数 $f: \{0,1\}^n \to \{0,1\}$ を未知の量子基底で計算するより一般的な問題も検討し、この問題に対して我々の量子多数決アルゴリズムの一般化が最適であることを示す。
一般化アルゴリズムの最適パラメータとその最悪の場合の忠実性は、サイズ$o(n)$の単純な線形プログラムによって決定できる。
アルゴリズムの時間複雑性は$O(n^4 \log n)$であり、$n$は入力量子ビットの数である。
関連論文リスト
- Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
我々は、$s$非ゼロ振幅を持つ$n$量子ビットスパース量子状態の準備を検討し、2つのアルゴリズムを提案する。
最初のアルゴリズムは$O(ns/log n + n)$ gatesを使用し、以前のメソッドを$O(log n)$で改善する。
2番目のアルゴリズムは、短いハミルトニアンパスを示す二進弦向けに調整されている。
論文 参考訳（メタデータ） (2024-04-08T02:13:40Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - 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) - Optimal (controlled) quantum state preparation and improved unitary
synthesis by quantum circuits with any number of ancillary qubits [20.270300647783003]
制御量子状態準備(CQSP)は、与えられた$n$-qubit状態に対するすべての$iin 0,1k$に対して、$|irangle |0nrangleから |irangle |psi_irangle $への変換を提供することを目的としている。
我々は、深さ$Oleft(n+k+frac2n+kn+k+mright)$とサイズ$Oleft(2n+kright)$のCQSPを実装するための量子回路を構築する。
論文 参考訳（メタデータ） (2022-02-23T04:19:57Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - Asymptotically Optimal Circuit Depth for Quantum State Preparation and
General Unitary Synthesis [24.555887999356646]
この問題は量子アルゴリズム設計、ハミルトニアンシミュレーション、量子機械学習において基本的な重要性を持っているが、その回路深さと大きさの複雑さは、アシラリー量子ビットが利用可能である時点では未解決のままである。
本稿では,$psi_vrangle$を奥行きで作成できる$m$Acillary qubitsを用いた量子回路の効率的な構築について検討する。
我々の回路は決定論的であり、状態を準備し、正確にユニタリを実行し、アシラリー量子ビットを厳密に利用し、深さは幅広いパラメータ状態において最適である。
論文 参考訳（メタデータ） (2021-08-13T09:47:11Z) - Low-depth Quantum State Preparation [3.540171881768714]
量子コンピューティングにおける重要なサブルーチンは、$N$複素数の古典的なデータを重ね合わせの$n=lceil logNrceil$-qubit状態の振幅にロードすることである。
ここでは、古典的データを用いた量子状態準備におけるこの時空トレードオフについて検討する。
我々は、$mathcal O(n2)$の回路深さを持つ量子アルゴリズムを提案し、任意の$N$複素数を符号化する。
論文 参考訳（メタデータ） (2021-02-15T13:11:43Z) - 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) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。