1,720,971 research outputs found
Безкомуникационни стратегии за Widening
Full text link[Ivanova-Rohling Violeta Nikolaeva; Иванова-Ролинг Виолета Николаева
Theoretical Properties of a Neighborhood-based Approach for Widening
Full text linkMost of the research in parallel data mining and machine learning algorithms is focused on improving the efficiency of existing algorithms. However, our focus is the improvement of the solution quality, or model accuracy. We are looking for "smart" strategies to invest parallel compute resources in order to achieve a better exploration of the search space by exploring several solutions in parallel, referred to as Widening. In this paper, we discuss the theoretical properties of a neighborhood-based Widening using a type of neighborhoods, optimality neighborhoods and contrast this communicationless approach to the straightforward beam-like Top-k Widening approach, which requires communication. We show a bound on the number of parallel workers needed for the communicationless approach to guarantee that it has a solution of the same quality as the Top-k approach. In addition to the theoretical comparison, we experimentally compare these two approaches in terms of running time and quality of final solution, using a widened version of the greedy algorithm for set cover problem
Communication-less Strategies for Widening
No full textWe live in the age of ever-increasing parallel computing resources, and as a consequence, for a decade there has been intense research into parallel data mining algorithms. Most of this research is focused on improving the running time of existing algorithms. In this dissertation we want to look at parallel data mining from a different perspective: instead of using the parallel versions of algorithms to obtain the solution with the same quality, only faster, we want to know how to invest parallel compute resources in a way which improves the quality of the solution. Because the space of potential solutions if typically enormous, and it cannot be explored through an exhaustive search to find the optimal solution, often the data mining algorithms use a heuristic (for example a greedy search) in order to find a sufficiently good solution in a reasonable time. Due to this limited exploration, finding the optimal solution is not guaranteed. The focus of this work is to develop strategies for investing parallel compute resources to improve the result obtained by standard greedy data mining heuristics by investing parallel resources into a better exploration of the (model) search space. We call this approach Widening of search heuristics. Additionally, we want to keep the running time of the algorithm as close to the running time of the original algorithm, as possible.The most trivial implementation of Widening is the simple beam search, Top-k Widening. This approach, however, requires continuous synchronization between the parallel workers. In order to avoid the consequent communication overhead, we are focused on Widening strategies, which explore the search space in a structured fashion, without the need for communication.We describe Ideal Widening, a theoretical framework for Widening, defined as an explicit partition of the search space with desired properties. Each partition is assigned for exploration to a given parallel worker. However, Ideal Widening is difficult to achieve in practice for a general type of search space. This is why we look at different communication-less Widening approaches, achievable in practice. These are typically based on the implicit partitioning of the search space via individualized modification of the selection operator for each parallel worker. Another problem of the Widening approaches to consider is the danger of converging to a local optimum. This is a well-known problem for the beam-search-based approaches and is solved by enforcing diversity. Achieving diversity of exploration without communication and without prior knowledge of the search space is not trivial. We introduce a simple approach, which assigns individual model preferences to each parallel worker, prior to the beginning of the search. This approach is parameter dependent and does not allow for a structured exploration of the search space, which is the goal of Widening. We define a neighborhood-based approach, Widening via neighborhoods, which aims at a structured exploration of the search space. Widening via neighborhoods defines neighborhoods of the locally optimal model with different properties and partitions them among the parallel workers, using labels assigned prior to the search. Three types of neighborhoods are investigated: optimality neighborhoods, for which the metric is based on the model quality measure; similarity neighborhoods, for which the metric is some type of model-based or data- based distance measure, and diversity neighborhoods, which contain diverse-and-good k models. Different approaches to diverse neighborhoods are described some are based on simple diversity thresholds, others use more sophisticated strategies such as nicheing. We demonstrate the theoretical properties of the neighborhood-based Widening approach, under fixed assumptions about the search space.publishe
Optimal Quantum State Tomography with Noisy Gates
Full text linkQuantum state tomography (QST) represents an essential tool for the
characterization, verification, and validation (QCVV) of quantum processors.
Only for a few idealized scenarios, there are analytic results for the optimal
measurement set for QST. E.g., in a setting of non-degenerate measurements, an
optimal minimal set of measurement operators for QST has eigenbases which are
mutually unbiased. However, in other set-ups, dependent on the rank of the
projection operators and the size of the quantum system, the optimal choice of
measurements for efficient QST needs to be numerically approximated. We have
generalized this problem by introducing the framework of customized efficient
QST. Here we extend customized QST and look for the optimal measurement set for
QST in the case where some of the quantum gates applied in the measurement
process are noisy. To achieve this, we use two distinct noise models: first,
the depolarizing channel, and second, over- and under-rotation in single-qubit
and to two-qubit gates (for further information, please see Methods). We
demonstrate the benefit of using entangling gates for the efficient QST
measurement schemes for two qubits at realistic noise levels, by comparing the
fidelity of reconstruction of our optimized QST measurement set to the
state-of-the-art scheme using only product bases.Comment: 18 pages, 6 figure
Optimal choice of state tomography quorum formed by projection operators
No full textA minimal set of measurement operators for quantum state tomography has in the nondegenerate case ideally eigenbases which are mutually unbiased. This is different for the degenerate case. Here we consider the situation where the measurement operators are projections on individual pure quantum states. This corresponds to maximal degeneracy. We present numerically optimized sets of projectors and find that they significantly outperform those which are taken from a set of mutually unbiased bases
Optimal Quantum State Tomography with Noisy Gates: Code for running Quantum State Tomography on IBM Manila
No full textWe provide here the code implementing quantum state tomography using qiskit and its StateTomography class (in qiskit_experiments.library). Here, the measurement bases are modified for two qubits to be a set of five mutually unbiased bases.
The file further includes the code for executing the state tomography on the IBM Manila device for varied number of shots. For comparison, quantum state tomography is also performed with the default measurement bases, which are nine separable bases
Quantum state tomography as a numerical optimization problem
No full textWe present a framework that formulates the quest for the most efficient quantum state tomography scheme as an optimization problem which can be solved numerically. This approach can be applied to a broad spectrum of relevant setups including measurements restricted to a subsystem. To illustrate the power of this method we present results for the six-dimensional Hilbert space constituted by a qubit-qutrit system, which could be realized e.g. by the N-14 nuclear spin-1 and two electronic spin states of a nitrogen-vacancy center in diamond. Measurements of the qubit subsystem are expressed by projectors of rank three, i.e., projectors on half-dimensional subspaces. For systems consisting only of qubits, it was shown analytically that a set of projectors on half-dimensional subspaces can be arranged in an informationally optimal fashion for quantum state tomography, thus forming so-called mutually unbiased subspaces. Our method goes beyond qubits-only systems and we find that in dimension six such a set of mutually-unbiased subspaces can be approximated with a deviation irrelevant for practical applications.publishe
Optimal choice of state tomography quorum formed by projection operators
Full text linkA minimal set of measurement operators for quantum state tomography has in the nondegenerate case ideally eigenbases which are mutually unbiased. This is different for the degenerate case. Here we consider the situation where the measurement operators are projections on individual pure quantum states. This corresponds to maximal degeneracy. We present numerically optimized sets of projectors and find that they significantly outperform those which are taken from a set of mutually unbiased bases.publishedVersion© 2019 American Physical Societ
Reinforcement learning approach for finding exchange-only gate sequences for CNOT with optimized gate time
No full textExchange-only quantum computation is a version of spin-based quantum computation that entirely avoids the difficulty of controlling individual spins by a magnetic field and instead functions by sequences of exchange pulses. The challenge for exchange-only quantum computation is to find short sequences that generate the required logical quantum gates. A reduction of the total gate time of such synthesized quantum gates can help to minimize the effects of decoherence and control errors during the gate operation and thus increase the total gate fidelity. We apply reinforcement learning to the optimization of exchange-gate sequences realizing the CNOT and CZ two-qubit gates which lend themselves to the construction of universal gate sets for quantum computation. We obtain a significant improvement regarding the total gate time compared to previously published results.publishe
- …
