Quantum estimation bound of Gaussian matrix permanent
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910782251335680 |
|---|---|
| author | Huh, Joonsuk |
| author_facet | Huh, Joonsuk |
| contents | Exact calculation and even multiplicative error estimation of matrix permanent are challenging for both classical and quantum computers. Regarding the permanents of random Gaussian matrices, the additive error estimation is closely linked to boson sampling, and achieving multiplicative error estimation requires exponentially many samplings. Our newly developed formula for matrix permanents and its corresponding quantum expression have enabled better estimation of the average additive error for random Gaussian matrices compared to Gurvits' classical sampling algorithm. The well-known Ryser formula has been converted into a quantum permanent estimator. When dealing with real random Gaussian square matrices of size $N$, the quantum estimator can approximate the matrix permanent with an additive error smaller than $ε(\sqrt{\mathrm{e}N})^{N}$, where $ε$ is the estimation precision. In contrast, Gurvits' classical sampling algorithm has an estimation error of $ε(2\sqrt{N})^{N}$, which is exponentially larger ($1.2^{N}$) than the quantum method. As expected, the quantum additive error bound fails to reach the multiplicative error bound of $(2πN)^{1/4}ε(\sqrt{N/\mathrm{e}})^{N}$. Additionally, the quantum permanent estimator can be up to quadratically faster than the classical estimator when using quantum phase estimation-based amplitude estimation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_01328 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Quantum estimation bound of Gaussian matrix permanent Huh, Joonsuk Quantum Physics Mathematical Physics Atomic Physics Computational Physics Exact calculation and even multiplicative error estimation of matrix permanent are challenging for both classical and quantum computers. Regarding the permanents of random Gaussian matrices, the additive error estimation is closely linked to boson sampling, and achieving multiplicative error estimation requires exponentially many samplings. Our newly developed formula for matrix permanents and its corresponding quantum expression have enabled better estimation of the average additive error for random Gaussian matrices compared to Gurvits' classical sampling algorithm. The well-known Ryser formula has been converted into a quantum permanent estimator. When dealing with real random Gaussian square matrices of size $N$, the quantum estimator can approximate the matrix permanent with an additive error smaller than $ε(\sqrt{\mathrm{e}N})^{N}$, where $ε$ is the estimation precision. In contrast, Gurvits' classical sampling algorithm has an estimation error of $ε(2\sqrt{N})^{N}$, which is exponentially larger ($1.2^{N}$) than the quantum method. As expected, the quantum additive error bound fails to reach the multiplicative error bound of $(2πN)^{1/4}ε(\sqrt{N/\mathrm{e}})^{N}$. Additionally, the quantum permanent estimator can be up to quadratically faster than the classical estimator when using quantum phase estimation-based amplitude estimation. |
| title | Quantum estimation bound of Gaussian matrix permanent |
| topic | Quantum Physics Mathematical Physics Atomic Physics Computational Physics |
| url | https://arxiv.org/abs/2205.01328 |