一種採樣隨機Clifford算子的簡單方法

2021-02-20 量子計算漫談


這篇文章提出了一種可以均勻隨機採樣Clifford算子的方法，相比於此前的採樣算法，該方法實現更為簡單，且可以直接生成Clifford算子對應的量子電路，同時在時間效率上也達到了目前最好的水平。

題目：A simple method for sampling random Clifford operators

作者：Ewout van den Berg

Scite：41次

ArXiv：2008.06011

Clifford群在量子信息與量子計算領域中都具有重要地位，在量子計算的經典模擬[1]、量子信道噪聲刻畫[2]等方面都有著重要的應用，而其中某些應用要求我們能夠高效地從Clifford群中進行均勻隨機採樣。在這篇文章中，作者基於Pauli矩陣的Tableau表示方法，提出了一種能夠對Clifford群進行均勻隨機採樣的算法。下面我們將介紹相關的一些數學概念與文章算法的具體過程。

對於單個qubit而言，Pauli群被定義為所有帶符號(

這一集合在矩陣乘法運算下構成一個群；

 

僅包含Hadamard門、相位門以及控制非門的量子電路實現，反之亦然[3]。

由於任意兩個Pauli算子

其中，因子


 圖1.  

前文提到了Clifford群可以通過單比特Hadamard門、相位門以及雙比特控制非門生成，而Tableau表示的好處就在於它能夠很方便地表示Pauli算子在Clifford算子作用下的變化：正如圖2所示，作用在qubit

         圖2. Hadamard門、相位門與控制非門作用圖示

算法的主要思路是將隨機Clifford算子的採樣問題轉換為採樣一個隨機Pauli算子的Tableau表示。

給定Clifford算子

而任意一個Pauli算子都可以寫成

假設


圖3. 3-qubit Pauli算子的基項

在以上轉換的基礎上，算法首先採樣一個隨機Pauli算子的Tableau表示，然後通過上文提到的Hadamard門，相位門與控制非門等操作將這張表變換為初始的Tableau表示，那麼由這些量子比特門構成的電路就是我們想要採樣的Clifford算子。

為了降低採樣的複雜度。本文採用了和文獻[5]類似的層次採樣技術，即每次只採樣表中兩行，先將這部分還原為初始的表（類似於高斯消元），下一次則在此基礎上再採樣兩行，重複以上操作，經過

圖4. 層次採樣過程圖示

算法中最重要的環節就是如何進行高效地採樣，作者提出了如下算法

對於第一行，隨機採樣一個非單位元的Pauli算子。由於每個Pauli算子都可以由一個

相比於此前的一些工作[4,5]，本文工作的主要優勢在於實現簡單，並且可以按照流式方式直接生成採樣得到的Clifford算子對應的量子電路，電路中的不同部分在算法中也可以並行生成；同時算法的時間複雜度為

[1] Aaronson S, Gottesman D. Improved simulation of stabilizer circuits[J]. Physical Review A, 2004, 70(5).

[2] Emerson J, Alicki R, Życzkowski K, et al. Scalable noise estimation with random unitary operators[J]. Journal of Optics B-quantum and Semiclassical Optics, 2005, 7(10).

[3] Nielsen M A, Chuang I. Quantum computation and quantum information[J]. 2002.

[4] Koenig R, Smolin J A. How to efficiently select an arbitrary Clifford group element[J]. Journal of Mathematical Physics, 2014, 55(12).

[5] Bravyi S, Maslov D. Hadamard-free circuits expose the structure of the clifford group[J]. arXiv preprint arXiv:2003.09412, 2020.

封面圖片來源於: https://www.inverse.com/article/30729-quantum-code-programming-quantum-mechanics-quantum-computers

相關焦點

  • 隨機採樣方法——蒙特卡羅方法
    》地址:http://www.cnblogs.com/pinard/p/6625739.html作為一種隨機採樣方法，馬爾科夫鏈蒙特卡羅（Markov Chain Monte Carlo，以下簡稱MCMC）在機器學習,深度學習以及自然語言處理等領域都有廣泛的應用，是很多複雜算法求解的基礎。
  • 基於序列模型的隨機採樣
    本文回顧了一系列常用的序列模型採樣方法，包括基於蒙特卡洛的隨機採樣和隨機束搜索，以及最近提出的基於Gumbel-Top-K的隨機束搜索。表1展示了這三種方法各自的優缺點。圖4 束搜索最終結果序列模型中的隨機採樣從序列模型中採集多個樣本有兩種經典的方法：基於蒙特卡洛的隨機採樣和基於蒙特卡洛的束搜索。
  • 當隨機採樣遇見插值,微軟亞研提出節省推理計算量的新範式
    在一篇 ECCV 2020 Oral 論文中，來自微軟亞洲研究院等機構的研究者提出了一種隨機採樣與插值相結合的新方法，可以有效降低節省推理的計算量。近年來，隨著深度學習的不斷發展，視覺領域出現了越來越多的高精度模型，但這些模型所需的計算量也越來越大。因此，如何在推理階段避免冗餘的計算在近年來成為研究熱點。
  • 機器學習的5種採樣方法介紹
    本文介紹了在處理數據時可以使用的一些最常見的採樣技術。 簡單隨機抽樣 假設您要選擇一個群體的子集，其中該子集的每個成員被選擇的概率都相等。 下面我們從一個數據集中選擇 100 個採樣點。 sample_df = df.sample（100） 分層採樣
  • 拉普拉斯算子的FPGA實現方法
    拉普拉斯算子是一種重要的圖像增強算子，它是一種各向同性濾波器，即濾波器的響應與濾波器作用圖像的突變方向無關，而且實現簡單，被廣泛用於圖像銳化和高頻增強等算法中。 在此，提出一種使用QuartusⅡ開發環境的Megafunctions功能模塊實現拉普拉斯算子的方案，可以做到實時增強圖像的高頻細節。
  • 算子
    在數學和計算機領域，算子是一個常見的概念，我們先來簡單理解一下，因為心理學的算子其實也只是在此基礎上的演變。算子英文一般稱為operator，直譯可以理解為操作。在數學上可以解釋成一個函數空間到另一個函數空間（或它自身）的映射。在計算機領域可以理解為一個處理單元，往往是指一個函數，在使用算子時往往會有輸入和輸出，算子則完成相應數據的轉化，比如：mov、inc等都是算子。
  • PySpark算子處理空間數據全解析(16): reduceByKey算子簡介(1)
    這個算子一般都是與Map算子組合起來使用的，一般來說:Map負責構建數據結構，reduceByKey算子負責進行聚合統計。Spark和Hadoop一類的框架，最早就是用來進行統計分析的，在屬性數據進行計算的時候，ReduceByKey是非常重要的一個操作，比如下面這個案例：
  • 數據科學家需要了解的 5 種採樣方法
    本文介紹了在處理數據時可以使用的一些最常見的採樣技術。簡單隨機抽樣假設您要選擇一個群體的子集，其中該子集的每個成員被選擇的概率都相等。下面我們從一個數據集中選擇 100 個採樣點。sample_df = df.sample(100)分層採樣假設我們需要估計選舉中每個候選人的平均票數。
  • 通過隨機採樣和數據增強來解決數據不平衡的問題
    從多數類中刪除樣本的過程稱為欠採樣，而將樣本添加到少數類中的過程稱為過採樣。隨機欠採樣是指多數類別的隨機採樣。進行該過程，直到達到少數群體的平衡為止。儘管此技術有助於在多數和少數類別之間建立平衡，但是從多數類中刪除樣本時可能會丟失重要信息。
  • Arxiv網絡科學論文摘要6篇(2021-01-13)
    //arxiv.org/abs/2101.04611作者： Tiandong Wang, Panpan Zhang摘要： 由於網絡數據的複雜性，我們提出了一種有向混合隨機網絡，該網絡將優先連接（PA）規則與統一附件（UA）規則混合在一起。
  • 2020-08-15 arxiv.cs.CV
    cn.arxiv.org/pdf/2008.05892  [14].Title: Alleviating Human-level Shift : A Robust Domain Adaptation Method for Multi-person Pose Estimation緩解人體水平漂移：一種穩健的域自適應多人位姿估計方法Authors:Xixia Xu;Qi Zou;Xue Lin;Comments: Accepted
  • 從算子角度理解優化方法
    ，而這些方法又可以從不同角度去理解。 ，迭代去尋找解： 的更新放在一起：   5.Peaceman-Rachford splitting這個算子的穩定點迭代等價於對稱ADMM方法。也就是：這個方法我第一次見是在何炳生老師（我老師的老師）的一個講座上，用變分不等式的框架去分析的，還舉了個挑擔子的例子，說兩邊一樣重（對稱）才能跑得快，印象深刻。1. 這些算子怎麼來的呢？用forward來舉例吧，我們本來要求
  • 說說隨機森林
    隨機森林對多元公線性不敏感，結果對缺失數據和非平衡的數據比較穩健，可以很好地預測多達幾千個解釋變量的作用（Breiman 2001b），被譽為當前最好的算法之一（Iverson et al. 2008）。隨機森林顧名思義，是用隨機的方式建立一個森林，森林裡面有很多的決策樹組成，隨機森林的每一棵決策樹之間是沒有關聯的。
  • 解讀TRPO論文,深度強化學習結合傳統優化方法
    （論文第二部分）基於 Kakade 論文中使用mixture policy保證每一步效果提升的方法，擴展到一般隨機策略，引入策略分布的total variation divergence作為約束。（論文第三部分）將total variation divergence約束替換成平均 KL divergence 約束，便於使用蒙特卡洛方法通過採樣來生成每一步的具體優化問題。
  • 數學都知道 — arXiv專輯(2020.12.2)
    美國數學系高級數學教授的文獻分析Bibliometric Analysis of Senior US Mathematics Facultyhttps://arxiv.org/abs/2008.11196本文介紹了一種方法，可以分析數學領域中的引用指標。
  • 科學家提出多自由度網絡架構協同搜索新方法
    但由於可微分網絡架構搜索中超網絡權重共享、單路徑採樣和寬度粗粒度離散性的搜索空間，搜索到的網絡架構很難同時達到準確性和資源約束上的最優。可微分網絡架構搜索仍有很多問題亟待解決。 近日，中國科學院自動化研究所智能感知與計算研究中心團隊從算子、深度和寬度三個自由度重新思考當前主流的可微分網絡架構搜索算法，通過實驗分析與驗證，提出一種新的網絡架構自動搜索方法，可穩定高效地從龐大的架構空間中搜索到高準確性的網絡架構，同時嚴格滿足時延約束。該
  • 機器學習之統計採樣方法和馬爾可夫過程(馬爾可夫鏈蒙特卡羅方法)匯總
    通過隨機採樣的方法，以隨機事件出現的頻率估計其概率，或者以採樣的數字特徵估算隨機變量的數字特徵，並將其作為問題的解，此種方法常用於求解複雜的高維積分問題    在實際的應用中，所要面對的第一個問題就是如何進行數據採樣，在計算機模擬中，通常所說的採樣指的是：從一個概率分布中生成觀察值的方法，且該分布通常是由它的概率密度函數決定並表示，但是結合之前所提到的無意識統計學家法則LOTUS
  • 機器學習中需要了解的 5 種採樣方法
    種採樣方法，編譯整理如下。現假設該國有 3 個城鎮：我們可以選擇在整個人口中隨機抽取一個 60 大小的樣本，但在這些城鎮中，隨機樣本可能不太平衡，因此會產生偏差，導致估計誤差很大。相反，如果我們選擇從 A、B 和 C 鎮分別抽取 10、20 和 30 個隨機樣本，那麼我們可以在總樣本大小相同的情況下，產生較小的估計誤差。