ACM Transactions on Quantum Computing

The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is \(O(\sqrt {N}) \) with an asymptotic probability of 1 + o (1), where N is the number of vertices.

Pedro Lugão

Renato Portugal

Mohamed Sabri

Hajime Tanaka

Multimarked Spatial Search by Continuous-Time Quantum Walk

连续时间量子漫步的多标记空间搜索

Estimating the state preparation fidelity of highly entangled states on noisy intermediate-scale quantum (NISQ) devices is important for benchmarking and application considerations. Unfortunately, exact fidelity measurements quickly become prohibitively expensive, as they scale exponentially as O (3 N ) for N -qubit states, using full state tomography with measurements in all Pauli bases combinations. However, Somma et al. established that the complexity could be drastically reduced when looking at fidelity lower bounds for states that exhibit symmetries, such as Dicke States and GHZ States. These bounds must still be tight enough for larger states to provide reasonable estimations on NISQ devices. For the first time and more than 15 years after the theoretical introduction, we report meaningful lower bounds for the state preparation fidelity of all Dicke States up to N = 10 and all GHZ states up to N = 20 on Quantinuum H1 ion-trap systems using efficient implementations of recently proposed scalable circuits for these states. Our achieved lower bounds match or exceed previously reported exact fidelities on superconducting systems for much smaller states. Furthermore, we provide evidence that for large Dicke States \(\vert {{D_{N}^{N}{/2}}\rangle } \) , we may resort to a GHZ-based approximate state preparation to achieve better fidelity. This work provides a path forward to benchmarking entanglement as NISQ devices improve in size and quality.

Shamminuj Aktar

Andreas Bärtschi

Abdel-Hameed A. Badawy

Stephan Eidenbenz

Scalable Experimental Bounds for Entangled Quantum State Fidelities

可扩展实验纠缠量子态保真度界限

We focus on the depth optimization of CNOT circuits on hardwares with limited connectivity. We adapt the algorithm from Kutin et al. [17] that implements any n -qubit CNOT circuit in depth at most 5 n on a Linear Nearest Neighbour (LNN) architecture. Our proposal is a block version of Kutin et al. ’s algorithm that is scalable with the number of interactions available in the hardware: the more interactions we have the less the depth. We derive better theoretical upper bounds and we provide a simple implementation of the algorithm. Overall, we achieve better depth complexity for CNOT circuits on some realistic quantum hardware like a grid or a ladder. For instance the execution of a n -qubit CNOT circuit on a grid can be done in depth 4 n + 8.

Timothée Goubault de Brugière

Simon Martiel

Shallower CNOT circuits on realistic quantum hardware

现实量子硬件上的更浅CNOT电路

Near-term intermediate scale quantum (NISQ) computers are likely to have very restricted hardware resources, where precisely controllable qubits are expensive, error-prone, and scarce. Programmers of such computers must therefore balance trade-offs among a large number of (potentially heterogeneous) factors specific to the targeted application and quantum hardware. To assist them, we propose Meta Quantum Circuits with Constraints (MQCC) , a meta-programming framework for quantum programs. Programmers express their application as a succinct collection of normal quantum circuits stitched together by a set of (manually or automatically) added meta-level choice variables, whose values are constrained according to a programmable set of quantitative optimization criteria. MQCC’s compiler generates the appropriate constraints and solves them via an SMT solver, producing an optimized, runnable program. We showcase a few MQCC’s applications for its generality including an automatic generation of efficient error syndrome extraction schemes for fault-tolerant quantum error correction with heterogeneous qubits and an approach to writing approximate quantum Fourier transformation and quantum phase estimation that smoothly trades off accuracy and resource use. We also illustrate that MQCC can easily encode prior one-off NISQ application designs- –multi-programming (MP) , crosstalk mitigation (CM) —as well as a combination of their optimization goals (i.e., a combined MP-CM).

Haowei Deng

Yuxiang Peng

Michael Hicks

Xiaodi Wu

Automating NISQ Application Design with Meta Quantum Circuits with Constraints (MQCC)

基于约束的元量子电路自动化设计用于NISQ应用

Quantum linear system algorithms (QLSA) have the potential to speed up Interior Point Methods (IPM). However, a major bottleneck is the inexactness of quantum Tomography to extract classical solutions from quantum states. In addition, QLSAs are sensitive to the condition number, and this sensitivity is exacerbated when the Newton systems arising in IPMs converge to a singular matrix. Recently, an Inexact Feasible Quantum IPM (IF-QIPM) has been developed that addresses the inexactness of QLSAs. However, this method requires a large number of gates and qubits to be implemented. Here, we propose a new IF-QIPM using the normal equation system, which requires less number of gates and qubits. To mitigate the sensitivity to the condition number and other input data-related parameters, we use preconditioning coupled with iterative refinement to obtain better complexity. Finally, we demonstrate the effectiveness of our approach on IBM Qiskit simulators.

Mohammadhossein Mohammadisiahroudi

Zeguan Wu

Brandon Augustino

Arielle Carr

Tamás Terlaky

Improvements to Quantum Interior Point Method for Linear Optimization

线性优化的量子内点方法改进

Efficient simulation of quantum circuits has become indispensable with the rapid development of quantum hardware. The primary simulation methods are based on state vectors and tensor networks. As the number of qubits and quantum gates grows larger in current quantum devices, traditional state-vector based quantum circuit simulation methods prove inadequate due to the overwhelming size of the Hilbert space and extensive entanglement. Consequently, brutal force tensor network simulation algorithms become the only viable solution in such scenarios. The two main challenges faced in tensor network simulation algorithms are optimal contraction path finding and efficient execution on modern computing devices, with the latter determines the actual efficiency. In this study, we investigate the optimization of such tensor network simulations on modern GPUs and propose general optimization strategies from two aspects: computational efficiency and accuracy. Firstly, we propose to transform critical Einstein summation operations into GEMM operations, leveraging the specific features of tensor network simulations to amplify the efficiency of GPUs. Secondly, by analyzing the data characteristics of quantum circuits, we employ extended precision to ensure the accuracy of simulation results and mixed precision to fully exploit the potential of GPUs, resulting in faster and more precise simulations. Our numerical experiments demonstrate that our approach can achieve a 3.96x reduction in verification time for random quantum circuit samples in the 18-cycle case of Sycamore, with sustained performance exceeding 21 TFLOPS on one A100. This method can be easily extended to the 20-cycle case, maintaining the same performance, accelerating by 12.5x compared to the state-of-the-art CPU-based results and 4.48-6.78x compared to the state-of-the-art GPU-based results reported in the literature. Furthermore, the strategies presented in this article hold general applicability for accelerating problems that can be tackled by contracting tensor networks such as graphical models and combinatorial optimizations.

Abbreviation	ACM Trans. Quantum Comput.
Journal Impact	3.72
Quartiles(Global)	QUANTUM SCIENCE & TECHNOLOGY(Q2)

Publication Information	Publisher: Association for Computing Machinery，Publishing cycle: ，Journal Type: journal，Open Access Journals: No
Basic data	Year of publication: 2020，Proportion of original research papers: ，Self Citation Rate:， Gold OA Rate:

ACM Transactions on Quantum Computing

Journal Citation Format

A journal article with 1 author

A journal article with 2 authors

A journal article with 3 authors

A journal article with 5 or more authors

Books Citation Format

Thesis Citation Format

Web sites Citation Format

Patent Citation Format

Staying up late manually editing references? ivySCI automatically matches journals and helps you generate references with a single click.

Share Submission Experience

Multimarked Spatial Search by Continuous-Time Quantum Walk

Scalable Experimental Bounds for Entangled Quantum State Fidelities

Shallower CNOT circuits on realistic quantum hardware

Automating NISQ Application Design with Meta Quantum Circuits with Constraints (MQCC)

Improvements to Quantum Interior Point Method for Linear Optimization

Multimarked Spatial Search by Continuous-Time Quantum Walk

Scalable Experimental Bounds for Entangled Quantum State Fidelities

Shallower CNOT circuits on realistic quantum hardware

Improvements to Quantum Interior Point Method for Linear Optimization

Efficient Quantum Circuit Simulation by Tensor Network Methods on Modern GPUs