Reqomp: 양자 회로에 대한 공간 제약이 있는 비계산

Reqomp: 양자 회로에 대한 공간 제약이 있는 비계산

Reqomp: 양자 회로 PlatoBlockchain 데이터 인텔리전스를 위한 공간 제약이 있는 비계산. 수직 검색. 일체 포함.

아누크 파라디스(Anouk Paradis), 벤저민 빅셀(Benjamin Bichsel), 마틴 베체프(Martin Vechev)

ETH 취리히, 스위스

이 논문이 흥미 롭거나 토론하고 싶습니까? SciRate에 댓글을 달거나 댓글 남기기.

추상

양자 회로는 큐비트 및 게이트 수에 대한 엄격한 제한이 있는 양자 컴퓨터에서 실행되어야 합니다. 두 한계를 모두 준수하는 회로를 생성하기 위한 유망한 기회는 $uncomputation$을 활용하여 큐비트를 게이트로 교환하는 것입니다. 우리는 하드웨어 제약 조건을 존중하면서 정확하고 효율적인 Ancillae의 비계산을 자동으로 합성하는 방법인 Reqomp를 제시합니다. 특정 회로에 대해 Reqomp는 엄격하게 제한되는 큐비트 수 또는 게이트 수 간에 광범위한 절충안을 제공할 수 있습니다. 우리의 평가는 Reqomp가 필요한 ancilla 큐비트 수를 최대 96%까지 크게 줄일 수 있음을 보여줍니다. 벤치마크의 80%에서 필요한 앤실라 큐비트는 25% 이상 줄어들 수 있지만 게이트 수가 28% 이상 증가하지 않습니다.

► BibTeX 데이터

► 참고 문헌

[1] Anouk Paradis, Benjamin Bichsel, Samuel Steffen 및 Martin Vechev. “Unqomp: 양자 회로에서 비계산 합성”. 프로그래밍 언어 설계 및 구현에 관한 제42차 ACM SIGPLAN 국제 회의 진행 중. 222~236페이지. 컴퓨팅 기계 협회, 뉴욕, 뉴욕, 미국(2021).
https : / /doi.org/ 10.1145 / 3453483.3454040

[2] Yongshan Ding, Xin-Chuan Wu, Adam Holmes, Ash Wiseth, Diana Franklin, Margaret Martonosi 및 Frederic T. Chong. “Square: 비용 효율적인 비계산을 통한 모듈식 양자 프로그램을 위한 전략적 양자 보조 도구 재사용”. 2020년 ACM/​IEEE 47차 연례 컴퓨터 아키텍처 국제 심포지엄(ISCA). 570~583페이지. IEEE(2020).
https://​/​doi.org/​10.1109/​ISCA45697.2020.00054

[3] 벤저민 빅셀, 막시밀리안 바더, 티몬 게르, 마틴 베체프. "Silq: 안전한 비계산 및 직관적인 의미를 갖춘 고급 양자 언어". 프로그래밍 언어 설계 및 구현에 관한 제41차 ACM SIGPLAN 컨퍼런스 진행 중. 286~300페이지. PLDI 2020미국 뉴욕주 뉴욕(2020). 컴퓨팅 기계 협회.
https : / /doi.org/ 10.1145 / 3385412.3386007

[4] 로버트 랜드, 제니퍼 페이킨, 이동호, 스티브 즈댄스윅. “ReQWIRE: 가역적 양자 회로에 대한 추론”. 이론 컴퓨터 과학 전자 논문집 287, 299–312 (2019).
https : / /doi.org/ 10.4204 / EPTCS.287.17

[5] 에마누엘 크닐. “베넷의 조약돌 게임 분석”. 기술 보고서 ​​arXiv:math/​9508218. arXiv(1995).
https:/ / doi.org/ 10.48550/ arXiv.math/ 9508218
arXiv : 수학 / 9508218

[6] 시우 만 찬, 마시모 로리아, 제이콥 노드스트롬, 마크 비냘스. "페블 게임에 대한 pspace 및 분리 결과의 근사 경도". 2015년 IEEE 56차 컴퓨터 과학 기초 연례 심포지엄에서. 466~485페이지. (2015).
https : / /doi.org/10.1109/focs.2015.36

[7] Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross, Peter Selinger 및 Benoît Valiron. “Quipper: 확장 가능한 양자 프로그래밍 언어”. 프로그래밍 언어 설계 및 구현에 관한 제34차 ACM SIGPLAN 컨퍼런스 진행 중. 333~342페이지. PLDI '13뉴욕, 뉴욕, 미국(2013). 컴퓨팅 기계 협회.
https : / /doi.org/ 10.1145 / 2491956.2462177

[8] Alex Parent, Martin Roetteler 및 Krysta M. Svore. “공간 제약이 있는 가역적 회로 편집”. 기술 보고서 ​​arXiv:1510.00377. arXiv(2015).
https://​/​doi.org/​10.48550/​arXiv.1510.00377
arXiv : 1510.00377

[9] Alex Parent, Martin Roetteler 및 Krysta M. Svore. “REVS: 공간 최적화된 가역 회로 합성을 위한 도구”. Iain Phillips와 Hafizur Rahaman은 Reversible Computation의 편집자입니다. 90~101페이지. 컴퓨터공학 강의노트참(2017). 스프링거 국제 출판.
https:/​/​doi.org/​10.1007/​978-3-319-59936-6_7

[10] Debjyoti Bhattacharjee, Mathias Soeken, Srijit Dutta, Anupam Chattopadhyay 및 Giovanni De Micheli. “계층적 양자 회로 합성에서 큐비트를 줄이기 위한 가역적 페블 게임”. 2019 IEEE 49차 다중값 논리 국제 심포지엄(ISMVL). 102~107페이지. (2019).
https:/ / doi.org/ 10.1109/ ISMVL.2019.00026

[11] Giulia Meuli, Mathias Soeken, Martin Roetteler, Nikolaj Bjorner 및 Giovanni De Micheli. “양자 메모리 관리를 위한 가역적 페블링 게임”. 2019 유럽 컨퍼런스 및 전시회의 설계, 자동화 및 테스트(DATE). 288~291페이지. IEEE(2019).
https://​/​doi.org/​10.23919/​date.2019.8715092

[12] 찰스 H. 베넷. “가역적 계산을 위한 시간/공간 절충”. 컴퓨팅에 관한 SIAM 저널 18, 766–776(1989).
https : / /doi.org/ 10.1137 / 0218053

[13] Krysta Svore, Alan Geller, Matthias Troyer, John Azariah, Christopher Granade, Bettina Heim, Vadym Kliuchnikov, Mariia Mykhailova, Andres Paz 및 Martin Roetteler. “Q#: 높은 수준의 DSL을 통해 확장 가능한 양자 컴퓨팅 및 개발 지원”. 실제 도메인 특정 언어 워크숍 2018 진행 중. RWDSL2018뉴욕, 뉴욕, 미국(2018). 컴퓨팅 기계 협회.
https : / /doi.org/ 10.1145 / 3183895.3183901

[14] 매튜 에이미, 마틴 로텔러, 크리스타 M. 스보레. "공간 효율적인 가역 회로의 검증된 편집". Rupak Majumdar 및 Viktor Kunčak에서는 컴퓨터 지원 검증(Computer Aided Verification) 편집자입니다. 10427권, 3~21페이지. 스프링거 국제 출판, 참(2017).
https:/​/​doi.org/​10.1007/​978-3-319-63390-9_1

인용

타임 스탬프 :

더보기 양자 저널