|
Vol.20
No.9&10, August
1, 2020
Research Articles:
Space-efficient quantum
multiplication polynomials for binary finite fields with sub-quadratoc
Toffoli gate count
(pp721-735)
Iggy
van Hoof
Multiplication is an essential
step in a lot of calculations. In this paper we look at multiplication
of 2 binary polynomials of degree at most
$n-1$,
modulo an irreducible polynomial of degree
$n$
with $2n$
input and $n$
output
qubits, without ancillary
qubits,
assuming no errors. With straightforward schoolbook methods this would
result in a quadratic number of
Toffoli
gates and a linear number of
CNOT
gates. This paper introduces a new algorithm that uses the same space,
but by utilizing space-efficient variants of
Karatsuba
multiplication methods it requires only
$O(n^{\log_2(3)})$
Toffoli
gates at the cost of a higher
CNOT
gate count: theoretically up to $O(n^2)$
but in examples the
CNOT
gate count looks a lot better.
Time evolution of
entanglement in a four-qubit Heisenberg chain
(pp736-746)
Hassan
Pakarzadeh, Zahra Norouzi, and Javad Vahedi
The phenomenon of quantum
entanglement has a very important role in quantum mechanics.
Particularly, the quantum spin chain provides a platform for theoretical
and experimental investigation of many-body entanglement. In this
paper, we investigate time evolution of entanglement in a four-qubit
anisotropic Heisenberg XXZ chain with nearest neighboring (NN),
the next nearest neighboring (NNN), and the Dzialoshinskii-Moriya
(DM) interactions. Calculations of the entanglement evolution of the
Werner state carried out in terms of concurrence for selected
ranges of control parameters such as DM interaction, frustration,
etc. The results show that for the Werner state, DM interaction and the
frustration parameters play important roles. Furthermore, results
show that the time evolution of the Werner state entanglement may
be useful to capture the quantum phase transitions in quantum magnetic
systems.
Efficient reversible
quantum design of sig-magnitude to two's complement converters
(pp747-765)
F.
Orts, G. Ortega, and E.M. GarzoŽn
Despite the great interest that
the scientific community has in quantum computing, the scarcity and high
cost of resources prevent to advance in this field. Specifically,
qubits
are very expensive to build, causing the few available quantum computers
are tremendously limited in their number of
qubits
and delaying their progress. This work presents new reversible circuits
that optimize the necessary resources for the conversion of a sign
binary number into two's complement of
$N$
digits. The benefits of our work are two: on the one hand, the proposed
two's complement converters are fault tolerant circuits and also are
more efficient in terms of resources (essentially, quantum cost, number
of
qubits, and T-count) than the
described in the literature. On the other hand, valuable information
about available converters and, what is more, quantum adders, is
summarized in tables for interested researchers. The converters have
been measured using robust metrics and have been compared with the
state-of-the-art circuits. The code to build them in a real quantum
computer is given.
Quantum-based algorithm and circuit
design for bounded Knapsack optimization problem
(pp766-786)
Wenjun
Hou and Marek Perkowski
The Knapsack Problem is a
prominent problem that is used in resource allocation and cryptography.
This paper presents an oracle and a circuit design that verifies
solutions to the decision problem form of the Bounded Knapsack Problem.
This oracle can be used by Grover Search to solve the optimization
problem form of the Bounded Knapsack Problem. This algorithm leverages
the quadratic speed-up offered by Grover Search to achieve a
quantum algorithm for the Knapsack Problem that shows improvement with
regard to classical algorithms. The quantum circuits were designed using
the Microsoft Q# Programming Language and verified on its local quantum
simulator. The paper also provides analyses of the complexity and gate
cost of the proposed oracle. The work in this paper is the first such
proposed method for the Knapsack Optimization Problem.
On the depth overhead
incurred when running quantum algorithms on near-term quantum computers
with limited qubit connectivity
(pp787-806)
Steven
Herbert
This paper addresses the problem
of finding the depth overhead that will be incurred when running quantum
circuits on near-term quantum computers. Specifically, it is envisaged
that near-term quantum computers will have low
qubit
connectivity: each
qubit
will only be able to interact with a subset of the other
qubits,
a reality typically represented by a
qubit
interaction graph in which a vertex represents a
qubit
and an edge represents a possible direct 2-qubit
interaction (gate). Thus the depth overhead is unavoidably incurred by
introducing \textit{swap}
gates into the quantum circuit to enable general
qubit
interactions. This paper proves that there exist quantum circuits where
a depth overhead in $\Omega(\log n)$
must necessarily be incurred when running quantum circuits with
$n$
qubits
on quantum computers whose
qubit
interaction graph has finite degree, but that such a logarithmic depth
overhead is achievable. The latter is shown by the construction of a
4-regular
qubit
interaction graph and associated compilation algorithm that can execute
any quantum circuit with only a logarithmic depth overhead.
back to QIC online Front page
|
