Abstract In nuclear magnetic resonance (NMR) quantum computing systems, it is very important to prepare an effective pure state rather than a true pure state. Our main objective is to present a general algorithm that provides quantum circuits for preparing an effective pure state from any mixed state, consisting only of controlled‐not (CNOT) quantum gates for homonuclear spin systems. Our algorithm is based on the product operator approach and could be applicable to NMR quantum computing systems with more than eight qubits. Optimization of the number of controlled‐not quantum gates is discussed. © 2005 Wiley Periodicals, Inc. Int J Quantum Chem, 2005
DNA computation could in principle solve the satisfiability (SAT) problem due to the operations in parallel on extremely large numbers of strands. We demonstrate some quantum gates corresponding to the DNA ones, based on which an implementation of DNA algorithm for SAT problem is available by quantum mechanical way. Since quantum computation owns the favorable feature of operations in parallel on 2
n states by using only n qubits, instead of 2
n strands in DNA computation, computational complexity is much reduced in treating the SAT problem quantum mechanically. We take a three-clause SAT problem with two variables as an example, and carry out a NMR experiment for solving a one-variable SAT problem.
To demonstrate the advantage of quantum computation, many attempts have been made to attack classically intractable problems, such as the satisfiability problem (SAT), with quantum computer. To use quantum algorithms to solve these NP-hard problems, a quantum oracle with quantum circuit implementation is usually required. In this manuscript, we first introduce a novel algorithm to synthesize quantum logic in the Conjunctive Normal Form (CNF) model. Compared with linear ancillary qubits in the implementation of Qiskit open-source framework, our algorithm can synthesize an m clauses n variables k-CNF with
O(k2m2/n) quantum gates by only using three ancillary qubits. Both the size and depth of the circuit can be further compressed with the increase in the number of ancillary qubits. When the number of ancillary qubits is
Ω(mϵ) (for any
ϵ>0), the size of the quantum circuit given by the algorithm is O(km), which is asymptotically optimal. Furthermore, we design another algorithm to optimize the depth of the quantum circuit with only a small increase in the size of the quantum circuit. Experiments show that our algorithms have great improvement in size and depth compared with the previous algorithms.
Exact synthesis is a key infrastructure in quantum circuit synthesis and optimization, which provides optimal implementations of small circuit shards and is widely used as a circuit re-synthesis optimization kernel. However, existing quantum exact synthesis methods suffer from encoding overhead, memory bottlenecks, and poor parallel scalability. In this work, we introduce a parallel exact synthesis framework for CNOT and phase polynomial circuits based on the semi-tensor product (STP) theory of matrices that avoids these issues. The algorithm contains two stages: it first enumerates candidate circuit topologies, and then instantiates each topology by determining the control and target qubit of its partial gates via a STP-based circuit solver. In the second stage, circuit topologies are encoded as canonical STP expressions, and the CNOT gates are synthesized through right-to-left STP matrix factorization that progressively eliminates infeasible gate decisions. In the framework, topology enumeration and the subsequent solving process are independent across different topologies, and can be naturally parallelized. Despite the NP-hardness of the problem, our algorithm yields up to
12.8× parallel speedup with 32 workers, whereas the parallel speedups of existing SAT-based methods remain below
5× with the same worker budget. On randomly generated synthesis targets, the proposed algorithm is typically
100-
1000× faster than the SAT-based approach on small and moderately difficult instances, and remains competitive for more difficult instances. When integrated in a real-world circuit optimization workflow, our algorithm achieves a median speedup of
3.41× on the QASMBench benchmark.
We demonstrate that the logic computation performed by the DNA-based algorithm for solving general cases of the satisfiability problem can be implemented by our proposed quantum algorithm on the quantum machine proposed by Deutsch. Moreover, we also prove that the logic computation by the bio-molecular operations proposed by Adleman can be implemented by quantum gates (for example, the Hadamard gate, NOT, CNOT, and CCNOT) on the quantum machine. Furthermore, those NP-complete problems solved on a bio-molecular computer are also solvable on a quantum computer. To test our theory, we carry out a three-qubit NMR experiment for solving the simplest satisfiability problem.
We show that quantum computation is possible with mixed states instead of pure states as inputs. This is performed by embedding within the mixed state a subspace that transforms like a pure state and that can be identified by labelling it based on logical (spin), temporal, or spatial degrees of freedom. This permits quantum computation to be realized with bulk ensembles far from the ground state. Experimental results are presented for quantum gates and circuits implemented with liquid nuclear magnetic resonance techniques and verified by quantum state tomography.