Portes multi-qubits à temps optimal : complexité, limites heuristiques et temporelles de porte efficaces

Portes multi-qubits à temps optimal : complexité, limites heuristiques et temporelles de porte efficaces

Horodatage: 13 mars 2024 8:59
Portes multi-qubits à temps optimal : complexité, heuristique efficace et limites de temps de porte PlatoBlockchain Data Intelligence. Recherche verticale. Aï.

Pascal Bassler1, Markus Heinrich1, et Martin Kliesch2

1Institut de physique théorique, Université Heinrich Heine de Düsseldorf, Allemagne
2Institut d'inspiration quantique et d'optimisation quantique, Université de technologie de Hambourg, Allemagne

Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.

Abstract

Les interactions intriquantes multi-qubits surviennent naturellement dans plusieurs plates-formes informatiques quantiques et promettent des avantages par rapport aux portes traditionnelles à deux qubits. En particulier, une interaction fixe de type Ising multi-qubits ainsi que des portes X à un seul qubit peuvent être utilisées pour synthétiser des portes ZZ globales (portes GZZ). Dans ce travail, nous montrons d’abord que la synthèse de telles portes quantiques optimales en temps est NP-difficile. Deuxièmement, nous fournissons des constructions explicites de portes multi-qubits spéciales à temps optimal. Ils ont des temps de porte constants et peuvent être implémentés avec de nombreuses couches de portes X de manière linéaire. Troisièmement, nous développons un algorithme heuristique avec une exécution polynomiale pour synthétiser des portes multi-qubits rapides. Quatrièmement, nous dérivons des limites inférieure et supérieure du temps de porte GZZ optimal. Sur la base de constructions explicites de portes GZZ et d'études numériques, nous conjecturons que n'importe quelle porte GZZ peut être exécutée en un temps O($n$) pour $n$ qubits. Notre algorithme de synthèse heuristique conduit à des temps de porte GZZ avec une mise à l'échelle similaire, ce qui est optimal en ce sens. Nous espérons que notre synthèse efficace de portes multi-qubits rapides permettra une exécution plus rapide et, par conséquent, plus résistante aux erreurs des algorithmes quantiques.

► Données BibTeX

► Références

X. Wang, A. Sørensen et K. Mølmer, Portes multibits pour l'informatique quantique, Phys. Rév. Lett. 86, 3907 (2001), arXiv:quant-ph/​0012055.
https: / / doi.org/ 10.1103 / PhysRevLett.86.3907
arXiv: quant-ph / 0012055

T. Monz, P. Schindler, JT Barreiro, M. Chwalla, D. Nigg, WA Coish, M. Harlander, W. Hänsel, M. Hennrich et R. Blatt, enchevêtrement de 14 qubits : Création et cohérence, Phys. Rév. Lett. 106, 130506 (2011), arXiv:1009.6126.
https: / / doi.org/ 10.1103 / PhysRevLett.106.130506
arXiv: 1009.6126

M. Kjaergaard, ME Schwartz, J. Braumüller, P. Krantz, JI-J. Wang, S. Gustavsson et WD Oliver, Qubits supraconducteurs : état des lieux actuel, Revue annuelle de la physique de la matière condensée 11, 369 (2020), arXiv : 1905.13641.
https: / / doi.org/ 10.1146 / annurev-conmatphys-031119-050605
arXiv: 1905.13641

C. Figgatt, A. Ostrander, NM Linke, KA Landsman, D. Zhu, D. Maslov et C. Monroe, Opérations d'emmêlement parallèles sur un ordinateur quantique universel à piège à ions, Nature 572, 368 (2019), arXiv: 1810.11948 .
https:/​/​doi.org/​10.1038/​s41586-019-1427-5
arXiv: 1810.11948

Y. Lu, S. Zhang, K. Zhang, W. Chen, Y. Shen, J. Zhang, J.-N. Zhang et K. Kim, Portes enchevêtrantes globales évolutives sur des qubits d'ions arbitraires, Nature 572, 363 (2019), arXiv : 1901.03508.
https:/​/​doi.org/​10.1038/​s41586-019-1428-4
arXiv: 1901.03508

P. Baßler, M. Zipper, C. Cedzich, M. Heinrich, PH Huber, M. Johanning et M. Kliesch, Synthèse et compilation avec des portes multi-qubits optimales dans le temps, Quantum 7, 984 (2023), arXiv :2206.06387.
https:/​/​doi.org/​10.22331/​q-2023-04-20-984
arXiv: 2206.06387

F. Barahona et AR Mahjoub, Sur le polytope coupé, Mathematical Programming 36, 157 (1986).
https: / / doi.org/ 10.1007 / BF02592023

MR Garey et DS Johnson, Ordinateurs et intraitabilité, Vol. 29 (WH Freeman and Company, New York, 2002).

MJ Bremner, A. Montanaro et DJ Shepherd, Complexité de cas moyenne versus simulation approximative des calculs quantiques de navettage, Phys. Le révérend Lett. 117, 080501 (2016), arXiv : 1504.07999.
https: / / doi.org/ 10.1103 / PhysRevLett.117.080501
arXiv: 1504.07999

J. Allcock, J. Bao, JF Doriguello, A. Luongo et M. Santha, Circuits à profondeur constante pour portes uniformément contrôlées et fonctions booléennes avec application aux circuits de mémoire quantique, arXiv : 2308.08539 (2023).
arXiv: 2308.08539

S. Bravyi, D. Maslov et Y. Nam, Implémentations à coût constant des opérations de Clifford et multiplication des portes contrôlées à l'aide d'interactions globales, Phys. Rév. Lett. 129, 230501 (2022), arXiv:2207.08691.
https: / / doi.org/ 10.1103 / PhysRevLett.129.230501
arXiv: 2207.08691

S. Bravyi et D. Maslov, les circuits sans Hadamard exposent la structure du groupe Clifford, IEEE Trans. Inf. Théorie 67, 4546 (2021), arXiv : 2003.09412.
https: / / doi.org/ 10.1109 / TIT.2021.3081415
arXiv: 2003.09412

D. Maslov et B. Zindorf, Optimisation de la profondeur des circuits CZ, CNOT et Clifford, IEEE Transactions on Quantum Engineering 3, 1 (2022), arxiv :2201.05215.
https: / / doi.org/ 10.1109 / TQE.2022.3180900
arXiv: 2201.05215

S. Boyd et L. Vandenberghe, Convex Optimization (Cambridge University Press, 2009).

E. Rich, Les classes de problèmes FP et FNP, dans Automates, calculabilité et complexité : théorie et applications (Pearson Education, 2007) pp. 510-511.
https://​/​www.cs.utexas.edu/​~ear/​cs341/​automatabook/​AutomataTheoryBook.pdf

M. Johanning, Chaînes d'ions linéaires isoespacées, Appl. Phys. B 122, 71 (2016).
https:/​/​doi.org/​10.1007/​s00340-016-6340-0

M. Laurent et S. Poljak, Sur une relaxation semi-définie positive du polytope coupé, Linear Algebra and its Applications 223-224, 439 (1995).
https:/​/​doi.org/​10.1016/​0024-3795(95)00271-R

MM Deza et M. Laurent, Geometry of Cuts and Metrics, 1ère éd., Algorithmes et combinatoires (Springer Berlin Heidelberg, 2009).
https:/​/​doi.org/​10.1007/​978-3-642-04295-9

ME-Nagy, M. Laurent et A. Varvitsiotis, Complexité du problème de complétion de matrice semi-définie positive avec une contrainte de rang, Springer International Publishing, 105 (2013), arXiv : 1203.6602.
https:/​/​doi.org/​10.1007/​978-3-319-00200-2_7
arXiv: 1203.6602

REAC Paley, Sur les matrices orthogonales, Journal of Mathematics and Physics 12, 311 (1933).
https://​/​doi.org/​10.1002/​sapm1933121311

A. Hedayat et WD Wallis, Matrices Hadamard et leurs applications, The Annals of Statistics 6, 1184 (1978).
https: / / doi.org/ 10.1214 / aos / 1176344370

H. Kharaghani et B. Tayfeh-Rezaie, Une matrice Hadamard d'ordre 428, Journal of Combinatorial Designs 13, 435 (2005).
https://​/​doi.org/​10.1002/​jcd.20043

D. Ž. Đoković, O. Golubitsky et IS Kotsireas, Quelques nouveaux ordres de matrices Hadamard et Skew-Hadamard, Journal of Combinatorial Designs 22, 270 (2014), arXiv : 1301.3671.
https://​/​doi.org/​10.1002/​jcd.21358
arXiv: 1301.3671

J. Cohn, M. Motta et RM Parrish, Diagonalisation de filtre quantique avec hamiltoniens à double factorisation compressés, PRX Quantum 2, 040352 (2021), arXiv: 2104.08957.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040352
arXiv: 2104.08957

DA Spielman et S.-H. Teng, Analyse lissée des algorithmes : pourquoi l'algorithme du simplexe prend généralement un temps polynomial, Journal of the ACM 51, 385 (2004), arXiv:cs/​0111050.
https: / / doi.org/ 10.1145 / 990308.990310
arXiv: cs / 0111050

S. Diamond et S. Boyd, CVXPY : un langage de modélisation intégré à Python pour l'optimisation convexe, J. Mach. Apprendre. Rés. 17, 1 (2016), arXiv : 1603.00943.
arXiv: 1603.00943
http: / / jmlr.org/ papers / v17 ​​/ 15-408.html

A. Agrawal, R. Verschueren, S. Diamond et S. Boyd, Un système de réécriture pour les problèmes d'optimisation convexe, J. Control Decis. 5, 42 (2018), arXiv:1709.04494.
https: / / doi.org/ 10.1080 / 23307706.2017.1397554
arXiv: 1709.04494

Free Software Foundation, GLPK (Kit de programmation linéaire GNU) (2012), version : 0.4.6.
https://​/​www.gnu.org/​software/​glpk/​

AT Phillips et JB Rosen, Un algorithme parallèle pour une minimisation globale quadratique concave contrainte, Mathematical Programming 42, 421 (1988).
https: / / doi.org/ 10.1007 / BF01589415

M. Dür, R. Horst et M. Locatelli, Conditions d'optimalité globale nécessaires et suffisantes pour la maximisation convexe revisitées, Journal of Mathematical Analysis and Applications 217, 637 (1998).
https://​/​doi.org/​10.1006/​jmaa.1997.5745

MS Bazaraa, HD Sherali et CM Shetty, Programmation non linéaire : théorie et algorithmes, 3e édition (John Wiley & sons, 2013).
https: / / doi.org/ 10.1002 / 0471787779

MA Hanson, Invexity et le théorème de Kuhn-Tucker, Journal of Mathematical Analysis and Applications 236, 594 (1999).
https://​/​doi.org/​10.1006/​jmaa.1999.6484

Cité par

Impossible de récupérer Données de référence croisée lors de la dernière tentative 2024-03-13 13:00:52: Impossible de récupérer les données citées par 10.22331 / q-2024-03-13-1279 de Crossref. C'est normal si le DOI a été enregistré récemment. Sur SAO / NASA ADS aucune donnée sur la citation des œuvres n'a été trouvée (dernière tentative 2024-03-13 13:00:52).

Cet article est publié dans Quantum sous le Creative Commons Attribution 4.0 International (CC BY 4.0) Licence. Le droit d'auteur reste la propriété des détenteurs d'origine tels que les auteurs ou leurs institutions.

Horodatage:

Plus de Journal quantique