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

CSI International Symposium on Computer Architecture and Digital Systems (CADS)

Extracting one-way quantum computation patterns from quantum circuits

Mahboobeh Houshmand, Mohammad Hossein Samavatian, Morteza Saheb Zamani, Mehdi Sedighi

Published May 1, 2012• 4 citations
Publisher

Abstract

In one-way quantum computations (1WQC), quantum correlations in an entangled state, called a cluster or graph state, are exploited to perform universal quantum computations using single-qubit measurements. The choices of bases for these measurements as well as the structure of the entanglements specify a quantum algorithm. The needed computations in this model are organized as patterns. Previously, an approach to extract a 1WQC pattern from a quantum circuit was proposed. The approach takes a quantum circuit consisting of only CZ andj(oc) gates and translates it into a 1WQC pattern after performing some known optimizations. However, most quantum synthesis algorithms decompose circuits using a library containing CNOT and any single-qubit gates. In this paper, we show how this approach can be modified in a way that it can take a circuit consisting of CNOT and any single-qubit gates as well as CZ and J(oc) gates to produce a 1WQC pattern. Experimental results show that adding CNOT gate directly to the pattern decreases the translation run-time.

DOI
10.1109/cads.2012.6316421

Related papers

Quantum Circuit Synthesis Targeting to Improve One-Way Quantum Computation Pattern Cost Metrics

Mahboobeh Houshmand, Mehdi Sedighi, Morteza Saheb Zamani +1 more

One-way quantum computation (1WQC) is a model of universal quantum computations in which a specific highly entangled state called acluster stateallows for quantum computation by single-qubit measurements. The needed computations in this model are organized as measurement patterns. The traditional approach to obtain a measurement pattern is by translating a quantum circuit that solely consists of CZ andJ(α) gates into the corresponding measurement patterns and then performing some optimizations by using techniques proposed for the 1WQC model. However, in these cases, the input of the problem is a quantum circuit, not an arbitrary unitary matrix. Therefore, in this article, we focus on the first phase—that is, decomposing a unitary matrix into CZ andJ(α) gates. Two well-known quantum circuit synthesis methods, namely cosine-sine decomposition and quantum Shannon decomposition are considered and then adapted for a library of gates containing CZ andJ(α), equipped with optimizations. By exploring the solution space of the combinations of these two methods in a bottom-up approach of dynamic programming, a multiobjective quantum circuit synthesis method is proposed that generates a set of quantum circuits. This approach attempts to simultaneously improve the measurement pattern cost metrics after the translation from this set of quantum circuits.

ACM Journal on Emerging Technologies in Computing Systems•May 21, 2017•10 citations

OWQS: One-Way Quantum Computation Simulator

Eesa Nikahd, Mahboobeh Houshmand, Morteza Saheb Zamani +1 more

In one-way quantum computation (1WQC) model, universal quantum computations are performed using measurements to designated qubits in a highly entangled state. The choices of basis for these measurements as well as the structure of the entanglements specify a quantum algorithm. Although a number of methods have been proposed to simulate quantum circuit model on classical computers, no efficient tool has been developed to simulate the 1WQC model directly. In this paper, some techniques such as qubit elimination, implicit and in-place matrix-vector multiplication and pattern reordering are utilized to considerably reduce the time and memory needed for the simulations. These techniques were implemented in a tool called One-Way Quantum computation Simulator (OWQS). Experimental results validate the efficiency of the proposed approach.

Euromicro Conference on Digital System Design (DSD)•Sep 1, 2012•2 citations

One-Way Quantum Computer Simulation

Eesa Nikahd, Mahboobeh Houshmand, Morteza Saheb Zamani +1 more

In one-way quantum computation (1WQC) model, universal quantum computations are performed using measurements to designated qubits in a highly entangled state. The choices of bases for these measurements as well as the structure of the entanglements specify a quantum algorithm. As scalable and reliable quantum computers have not been implemented yet, quantum computation simulators are the only widely available tools to design and test quantum algorithms. However, simulating the quantum computations on a standard classical computer in most cases requires exponential memory and time. In this paper, a general direct simulator for 1WQC, called OWQS, is presented. Some techniques such as qubit elimination, pattern reordering and implicit simulation of actions are used to considerably reduce the time and memory needed for the simulations. Moreover, our simulator is adjusted to simulate the measurement patterns with a generalized flow without calculating the measurement probabilities which is called extended one-way quantum computation simulator (EOWQS). Experimental results validate the feasibility of the proposed simulators and that OWQS and EOWQS are faster as compared with the well-known quantum circuit simulators, i.e., QuIDDPro and libquantum for simulating 1WQC model.

arXiv:1604.05659•Dec 10, 2015•0 citations

Parallel Quantum Circuit Extraction from MBQC-Patterns

Marcel Quanz, Korbinian Staudacher, Karl Fürlinger

In the model of measurement-based quantum computing (MBQC), computations are performed via sequential measurements on a highly entangled graph state. MBQC is a natural model for photonic quantum computing and has been shown to be useful for tasks like optimization and verification of general quantum computations. Therefore, it is often necessary to translate between MBQC and the predominantly used quantum circuit model in a fast and reliable way. While there are algorithms with linear complexity to extract quantum circuits from measurement patterns using additional ancilla qubits, efficient ancilla-free extraction has shown to be more costly. We develop strategies to parallelize an existing extraction algorithm based on ZX-calculus by exploiting the graph structure of measurement patterns and evaluate the performance on patterns obtained from a benchmark set of quantum circuits. Our results suggest that possible parallelization speedups are closely related to the graph structure of a pattern.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 27, 2024•0 citations

Geometry-based signal shifting of one-way quantum computation measurement patterns

Maryam Eslamy, Mahboobeh Houshmand, Morteza Saheb Zamani +1 more

In one-way quantum computation (1WQC) model, an initial highly entangled state called a graph state is used to perform universal quantum computations by a sequence of adaptive single-qubit measurements and post-measurement Pauli-X and Pauli-Z corrections. The needed computations are organized as measurement patterns or simply patterns in the 1WQC model. The entanglement operations in a pattern can be shown by a graph which together with the set of its input and output qubits is called the geometry of the pattern. Causal flow is a sufficient condition to identify a dependency structure for measurement sequences in order to obtain determinism. Signal shifting is an optimization technique which uses a set of rewrite rules to propagate the Pauli-Z corrections on the measured qubits to the end of patterns. However, automatically applying these rules has difficulties for implementation and is time consuming due to using many ineffective commutation rules. To overcome this problem, in this paper, a new automatic approach is proposed to perform signal shifting on patterns with flows based on their geometries instead of using rewriting rules. It is shown that the time complexity of the proposed approach is improved compared to the previous ones.

Iranian Conference on Electrical Engineering•May 1, 2016•3 citations

Compact quantum circuits from one-way quantum computation

Raphael Dias da Silva, Ernesto F. Galvão

In this paper we address the problem of translating one-way quantum computation (1WQC) into the circuit model. We start by giving a straightforward circuit representation of any 1WQC, at the cost of introducing many ancilla wires. We then propose a set of simple circuit identities that explore the relationship between the entanglement resource and correction structure of a 1WQC, allowing one to obtain equivalent circuits acting on fewer qubits. We conclude with some examples and a discussion of open problems.

arXiv:1209.5079•Physical Review A•Jul 19, 2013•9 citations
In one-way quantum computations (1WQC), quantum correlations in an entangled state, called a cluster or graph state, are exploited to perform universal quantum computations using single-qubit measurements. The choices of bases for these measurements as well as the structure of the entanglements specify a quantum algorithm. The needed computations in this model are organized as patterns. Previously, an approach to extract a 1WQC pattern from a quantum circuit was proposed. The approach takes a quantum circuit consisting of only CZ andj(oc) gates and translates it into a 1WQC pattern after performing some known optimizations. However, most quantum synthesis algorithms decompose circuits using a library containing CNOT and any single-qubit gates. In this paper, we show how this approach can be modified in a way that it can take a circuit consisting of CNOT and any single-qubit gates as well as CZ and J(oc) gates to produce a 1WQC pattern. Experimental results show that adding CNOT gate directly to the pattern decreases the translation run-time.
One-way quantum computation (1WQC) is a model of universal quantum computations in which a specific highly entangled state called acluster stateallows for quantum computation by single-qubit measurements. The needed computations in this model are organized as measurement patterns. The traditional approach to obtain a measurement pattern is by translating a quantum circuit that solely consists of CZ andJ(α) gates into the corresponding measurement patterns and then performing some optimizations by using techniques proposed for the 1WQC model. However, in these cases, the input of the problem is a quantum circuit, not an arbitrary unitary matrix. Therefore, in this article, we focus on the first phase—that is, decomposing a unitary matrix into CZ andJ(α) gates. Two well-known quantum circuit synthesis methods, namely cosine-sine decomposition and quantum Shannon decomposition are considered and then adapted for a library of gates containing CZ andJ(α), equipped with optimizations. By exploring the solution space of the combinations of these two methods in a bottom-up approach of dynamic programming, a multiobjective quantum circuit synthesis method is proposed that generates a set of quantum circuits. This approach attempts to simultaneously improve the measurement pattern cost metrics after the translation from this set of quantum circuits.
In one-way quantum computation (1WQC) model, universal quantum computations are performed using measurements to designated qubits in a highly entangled state. The choices of basis for these measurements as well as the structure of the entanglements specify a quantum algorithm. Although a number of methods have been proposed to simulate quantum circuit model on classical computers, no efficient tool has been developed to simulate the 1WQC model directly. In this paper, some techniques such as qubit elimination, implicit and in-place matrix-vector multiplication and pattern reordering are utilized to considerably reduce the time and memory needed for the simulations. These techniques were implemented in a tool called One-Way Quantum computation Simulator (OWQS). Experimental results validate the efficiency of the proposed approach.
In one-way quantum computation (1WQC) model, universal quantum computations are performed using measurements to designated qubits in a highly entangled state. The choices of bases for these measurements as well as the structure of the entanglements specify a quantum algorithm. As scalable and reliable quantum computers have not been implemented yet, quantum computation simulators are the only widely available tools to design and test quantum algorithms. However, simulating the quantum computations on a standard classical computer in most cases requires exponential memory and time. In this paper, a general direct simulator for 1WQC, called OWQS, is presented. Some techniques such as qubit elimination, pattern reordering and implicit simulation of actions are used to considerably reduce the time and memory needed for the simulations. Moreover, our simulator is adjusted to simulate the measurement patterns with a generalized flow without calculating the measurement probabilities which is called extended one-way quantum computation simulator (EOWQS). Experimental results validate the feasibility of the proposed simulators and that OWQS and EOWQS are faster as compared with the well-known quantum circuit simulators, i.e., QuIDDPro and libquantum for simulating 1WQC model.
In the model of measurement-based quantum computing (MBQC), computations are performed via sequential measurements on a highly entangled graph state. MBQC is a natural model for photonic quantum computing and has been shown to be useful for tasks like optimization and verification of general quantum computations. Therefore, it is often necessary to translate between MBQC and the predominantly used quantum circuit model in a fast and reliable way. While there are algorithms with linear complexity to extract quantum circuits from measurement patterns using additional ancilla qubits, efficient ancilla-free extraction has shown to be more costly. We develop strategies to parallelize an existing extraction algorithm based on ZX-calculus by exploiting the graph structure of measurement patterns and evaluate the performance on patterns obtained from a benchmark set of quantum circuits. Our results suggest that possible parallelization speedups are closely related to the graph structure of a pattern.
In one-way quantum computation (1WQC) model, an initial highly entangled state called a graph state is used to perform universal quantum computations by a sequence of adaptive single-qubit measurements and post-measurement Pauli-X and Pauli-Z corrections. The needed computations are organized as measurement patterns or simply patterns in the 1WQC model. The entanglement operations in a pattern can be shown by a graph which together with the set of its input and output qubits is called the geometry of the pattern. Causal flow is a sufficient condition to identify a dependency structure for measurement sequences in order to obtain determinism. Signal shifting is an optimization technique which uses a set of rewrite rules to propagate the Pauli-Z corrections on the measured qubits to the end of patterns. However, automatically applying these rules has difficulties for implementation and is time consuming due to using many ineffective commutation rules. To overcome this problem, in this paper, a new automatic approach is proposed to perform signal shifting on patterns with flows based on their geometries instead of using rewriting rules. It is shown that the time complexity of the proposed approach is improved compared to the previous ones.
In this paper we address the problem of translating one-way quantum computation (1WQC) into the circuit model. We start by giving a straightforward circuit representation of any 1WQC, at the cost of introducing many ancilla wires. We then propose a set of simple circuit identities that explore the relationship between the entanglement resource and correction structure of a 1WQC, allowing one to obtain equivalent circuits acting on fewer qubits. We conclude with some examples and a discussion of open problems.