Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEICE ESS FUNDAMENTALS REVIEW

Optimization Problems in Quantum Circuit Design

Shigeru Yamashita

Published Mar 31, 2021• 0 citations
Publisher

Abstract

将来大規模な量子計算を実現できるようになったときには，「量子回路設計」と呼ばれる作業が必要となる．これは，これまでの計算機向けの「回路設計」と同様にある種の最適化問題を解く作業と見ることができる．本稿では，量子回路設計において最適化を目指すべきと考えられている量子回路のコストの指標を幾つか紹介する．その中でも，近年精力的に研究されているNearest Neighbor Cost (NNC)を最適化する手法について紹介する．

DOI
10.1587/essfr.14.4_337

Related papers

Exact Synthesis of Nearest Neighbor Compliant Quantum Circuits in 2-D Architecture and Its Application to Large-Scale Circuits

Jingwen Ding, Shigeru Yamashita

In this paper, we propose an exact method of directly synthesizing a nearest neighbor compliant (NNC) quantum circuit with the smallest depth in 2-D architecture, given a reversible function. Our method maps the synthesis problem to a Boolean satisfiability (SAT) problem and uses a satisfiability modulo theories (SMT) solver to find an assignment of a network of allowed quantum gates. Since an SMT solver performs an exhaustive search, it can be ensured that on a specific qubit placement, the NNC quantum circuit synthesized by our method has the smallest number of quantum gates. However, the exhaustive search also makes our exact method not scale well. For that reason, we propose another method of applying our exact method in the local synthesis of large-scale circuits, to in parallel synthesize sub-NNC quantum circuits. From the experimental results, the quantum costs of the NNC quantum circuits synthesized by our methods are reduced by an average of 23.89%, when compared to an optimal heuristic method which determines the smallest number of SWAP gates in 2-D architecture.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Mar 27, 2019•26 citations

Control problems in quantum systems

Rebing, Wu, Jing +7 more

过去的十年或二在量控制技术的理论和实践见证巨大的进步。衔接从基本粒子物理到纳米技术的不同科学学科，量控制的目标是开发有效、有效的工具因为普通分析和设计，而是更多将重要地为未来铺平道路工艺的应用程序。这篇文章简短从当模特儿，分析和图案的观点考察基本的量控制理论，以及考虑未来研究方向。

中国科学通报：英文版•Jan 1, 2012•0 citations

Design and synthesis of efficient circuits for quantum computers

Αρχιμήδης Παυλίδης

Οι πρόσφατες εξελίξεις στον τομέα της πειραματικής κατασκευής κβαντικών υπολογιστών με εξαρτήματα αυξημένης αξιοπιστίας δείχνει ότι η κατασκευή τέτοιων μεγάλων μηχανών βασισμένων στις αρχές της κβαντικής φυσικής είναι πιθανή στο κοντινό μέλλον. Καθώς το μέγεθος των μελλοντικών κβαντικών υπολογιστών θα αυξάνεται, η σχεδίαση αποδοτικότερων κβαντικών κυκλωμάτων και μεθόδων σχεδίασης θα αποκτήσει σταδιακά πρακτικό ενδιαφέρον. Η συνεισφορά της διατριβής στην κατεύθυνση της σχεδίασης αποδοτικών κβαντικών κυκλωμάτων είναι διττή: Η πρώτη είναι η σχεδίαση καινοτόμων αποδοτικών αριθμητικών κβαντικών κυκλωμάτων βασισμένων στον Κβαντικό Μετασχηματισμό Fourier (QFT), όπως πολλαπλασιαστής-με-σταθερά-συσσωρευτής (MAC) και διαιρέτης με σταθερά, με γραμμικό βάθος (ή ταχύτητα) ως προς τον αριθμό ψηφίων των ακεραίων. Αυτά τα κυκλώματα συνδυάζονται αποτελεσματικά ώστε να επιτελέσουν την πράξη του modulo πολλαπλασιασμού με σταθερά με γραμμική πολυπλοκότητα χρόνου και χώρου και συνεπώς μπορούν να επιτελέσουν την πράξη της modulo εκθετικοποίησης (modular exponentiation) με τετραγωνική πολυπλοκότητα χρόνου και γραμμική πολυπλοκότητα χώρου. Οι πράξεις της modulo εκθετικοποίησης και του modulo πολλαπλασιασμού είναι αναπόσπαστα μέρη του σημαντικού κβαντικού αλγορίθμου παραγοντοποίησης του Shor, αλλά και άλλων κβαντικών αλγορίθμων της ίδιας οικογένειας, γνωστών ως κβαντική εκτίμηση φάσης (Quantum Phase Estimation). Αντιμετωπίζονται με αποτελεσματικό τρόπο σημαντικά προβλήματα υλοποίησης, που σχετίζονται με την απαίτηση χρήσης κβαντικών πυλών περιστροφής υψηλής ακρίβειας, καθώς και της χρήσης τοπικών επικοινωνιών. Η δεύτερη συνεισφορά της διατριβής είναι μία γενική μεθοδολογία ιεραρχικής σύνθεσης κβαντικών και αντιστρέψιμων κυκλωμάτων αυθαίρετης πολυπλοκότητας και μεγέθους. Η ιεραρχική μέθοδος σύνθεσης χειρίζεται καλύτερα μεγάλα κυκλώματα σε σχέση με τις επίπεδες μεθόδους σύνθεσης. Η προτεινόμενη μέθοδος προσφέρει πλεονεκτήματα σε σχέση με τις συνήθεις ιεραρχικές συνθέσεις που χρησιμοποιούν την μέθοδο "υπολογισμός-αντιγραφή-αντίστροφος υπολογισμός" του Bennett.

•Dec 1, 2016•0 citations

Exploiting Negative Control Lines and Nearest Neighbor for Improved Comparator Design

Tathagato Bose, Kamalika Datta, Indranil Sengupta

In this paper, improved reversible comparator designs are investigated using Multiple Control Toffoli (MCT) gates, improving Quantum Cost (QC) and also Nearest Neighbor Cost (NNC) metrics of circuits. The proposed designs are compared with recent works and found to be efficient in terms of cost by making these nearest neighbor compliant using Swap gate insertions.

International Conference on VLSI Design•Jan 1, 2019•1 citation

Synthesis of Reversible Functions Beyond Gate Count and Quantum Cost

Robert Wille, Mehdi Saeedi, Rolf Drechsler

Many synthesis approaches for reversible and quantum logic have been proposed so far. However, most of them generate circuits with respect to simple metrics, i.e. gate count or quantum cost. On the other hand, to physically realize reversible and quantum hardware, additional constraints exist. In this paper, we describe cost metrics beyond gate count and quantum cost that should be considered while synthesizing reversible and quantum logic for the respective target technologies. We show that the evaluation of a synthesis approach may differ if additional costs are applied. In addition, a new cost metric, namely Nearest Neighbor Cost (NNC) which is imposed by realistic physical quantum architectures, is considered in detail. We discuss how existing synthesis flows can be extended to generate optimal circuits with respect to NNC while still keeping the quantum cost small.

arXiv:1004.4609•Apr 26, 2010•38 citations

An Overview of Quantum Algorithms

Seiichiro Tani

量子コンピュータは，量子力学の原理を用いて計算を行うコンピュータであり，現在のコンピュータを超える計算能力を発揮することが期待されている．そのためには，量子コンピュータのハードウェアを効果的に使って計算を行うアルゴリズム（量子アルゴリズム）が必要となる．本稿では，これまで行われてきた量子アルゴリズム研究を概観し，課題と展望について議論する

Denshi Jouhou Tsuushin Gakkai Tsuushin Sosaieti magajin/B-plus/Denshi Jouhou Tsuushin Gakkai Tsuushin Sosaeti magajin•Jan 1, 2020•0 citations
将来大規模な量子計算を実現できるようになったときには，「量子回路設計」と呼ばれる作業が必要となる．これは，これまでの計算機向けの「回路設計」と同様にある種の最適化問題を解く作業と見ることができる．本稿では，量子回路設計において最適化を目指すべきと考えられている量子回路のコストの指標を幾つか紹介する．その中でも，近年精力的に研究されているNearest Neighbor Cost (NNC)を最適化する手法について紹介する．
In this paper, we propose an exact method of directly synthesizing a nearest neighbor compliant (NNC) quantum circuit with the smallest depth in 2-D architecture, given a reversible function. Our method maps the synthesis problem to a Boolean satisfiability (SAT) problem and uses a satisfiability modulo theories (SMT) solver to find an assignment of a network of allowed quantum gates. Since an SMT solver performs an exhaustive search, it can be ensured that on a specific qubit placement, the NNC quantum circuit synthesized by our method has the smallest number of quantum gates. However, the exhaustive search also makes our exact method not scale well. For that reason, we propose another method of applying our exact method in the local synthesis of large-scale circuits, to in parallel synthesize sub-NNC quantum circuits. From the experimental results, the quantum costs of the NNC quantum circuits synthesized by our methods are reduced by an average of 23.89%, when compared to an optimal heuristic method which determines the smallest number of SWAP gates in 2-D architecture.
Οι πρόσφατες εξελίξεις στον τομέα της πειραματικής κατασκευής κβαντικών υπολογιστών με εξαρτήματα αυξημένης αξιοπιστίας δείχνει ότι η κατασκευή τέτοιων μεγάλων μηχανών βασισμένων στις αρχές της κβαντικής φυσικής είναι πιθανή στο κοντινό μέλλον. Καθώς το μέγεθος των μελλοντικών κβαντικών υπολογιστών θα αυξάνεται, η σχεδίαση αποδοτικότερων κβαντικών κυκλωμάτων και μεθόδων σχεδίασης θα αποκτήσει σταδιακά πρακτικό ενδιαφέρον. Η συνεισφορά της διατριβής στην κατεύθυνση της σχεδίασης αποδοτικών κβαντικών κυκλωμάτων είναι διττή: Η πρώτη είναι η σχεδίαση καινοτόμων αποδοτικών αριθμητικών κβαντικών κυκλωμάτων βασισμένων στον Κβαντικό Μετασχηματισμό Fourier (QFT), όπως πολλαπλασιαστής-με-σταθερά-συσσωρευτής (MAC) και διαιρέτης με σταθερά, με γραμμικό βάθος (ή ταχύτητα) ως προς τον αριθμό ψηφίων των ακεραίων. Αυτά τα κυκλώματα συνδυάζονται αποτελεσματικά ώστε να επιτελέσουν την πράξη του modulo πολλαπλασιασμού με σταθερά με γραμμική πολυπλοκότητα χρόνου και χώρου και συνεπώς μπορούν να επιτελέσουν την πράξη της modulo εκθετικοποίησης (modular exponentiation) με τετραγωνική πολυπλοκότητα χρόνου και γραμμική πολυπλοκότητα χώρου. Οι πράξεις της modulo εκθετικοποίησης και του modulo πολλαπλασιασμού είναι αναπόσπαστα μέρη του σημαντικού κβαντικού αλγορίθμου παραγοντοποίησης του Shor, αλλά και άλλων κβαντικών αλγορίθμων της ίδιας οικογένειας, γνωστών ως κβαντική εκτίμηση φάσης (Quantum Phase Estimation). Αντιμετωπίζονται με αποτελεσματικό τρόπο σημαντικά προβλήματα υλοποίησης, που σχετίζονται με την απαίτηση χρήσης κβαντικών πυλών περιστροφής υψηλής ακρίβειας, καθώς και της χρήσης τοπικών επικοινωνιών. Η δεύτερη συνεισφορά της διατριβής είναι μία γενική μεθοδολογία ιεραρχικής σύνθεσης κβαντικών και αντιστρέψιμων κυκλωμάτων αυθαίρετης πολυπλοκότητας και μεγέθους. Η ιεραρχική μέθοδος σύνθεσης χειρίζεται καλύτερα μεγάλα κυκλώματα σε σχέση με τις επίπεδες μεθόδους σύνθεσης. Η προτεινόμενη μέθοδος προσφέρει πλεονεκτήματα σε σχέση με τις συνήθεις ιεραρχικές συνθέσεις που χρησιμοποιούν την μέθοδο "υπολογισμός-αντιγραφή-αντίστροφος υπολογισμός" του Bennett.
Many synthesis approaches for reversible and quantum logic have been proposed so far. However, most of them generate circuits with respect to simple metrics, i.e. gate count or quantum cost. On the other hand, to physically realize reversible and quantum hardware, additional constraints exist. In this paper, we describe cost metrics beyond gate count and quantum cost that should be considered while synthesizing reversible and quantum logic for the respective target technologies. We show that the evaluation of a synthesis approach may differ if additional costs are applied. In addition, a new cost metric, namely Nearest Neighbor Cost (NNC) which is imposed by realistic physical quantum architectures, is considered in detail. We discuss how existing synthesis flows can be extended to generate optimal circuits with respect to NNC while still keeping the quantum cost small.
量子コンピュータは，量子力学の原理を用いて計算を行うコンピュータであり，現在のコンピュータを超える計算能力を発揮することが期待されている．そのためには，量子コンピュータのハードウェアを効果的に使って計算を行うアルゴリズム（量子アルゴリズム）が必要となる．本稿では，これまで行われてきた量子アルゴリズム研究を概観し，課題と展望について議論する