We introduce a "Statistical Query Sampling" model, in which the goal of an algorithm is to produce an element in a hidden set S subset of or equal to {0, 1}(n) with reasonable probability The algorithm gains...
详细信息
ISBN:
(纸本)0769518796
We introduce a "Statistical Query Sampling" model, in which the goal of an algorithm is to produce an element in a hidden set S subset of or equal to {0, 1}(n) with reasonable probability The algorithm gains information about S through oracle calls (statistical queries), where the algorithm submits a query function g (.) and receives an approximation to Pr-xepsilonS[9(X) = 1] We show how this model is related to NMR quantum computing, in which only statistical properties of an ensemble of quantum systems can be measured, and in particular to the question of whether one can translate standard quantumalgorithms to the NMR setting without putting all of their classical post-processing into the quantum system. Using Fourier analysis techniques developed in the related context of statistical query learning, we prove a number of lower bounds (both information-theoretic and cryptographic) on the ability of algorithms to produces an x epsilon S, even when the set S is fairly simple. These lower bounds point out a difficulty in efficiently applying NMR quantum computing to algorithms such as Shor's and Simon's algorithm that involve significant classical post-processing. We also explicitly relate the notion of statistical query sampling to that of statistical query learning.
The analysis and use of visual information is a first order task for AI researchers. Due to the architecture of classical computers and to the computational complexity of state-of-the-art algorithms, it is required to...
详细信息
The analysis and use of visual information is a first order task for AI researchers. Due to the architecture of classical computers and to the computational complexity of state-of-the-art algorithms, it is required to find better ways to store, process and retrieve information for image processing. One plausible and exciting approach is quantuminformationprocessing (QIP). In this poster we present an initial step towards the definition of an emerging field, quantum Image processing, by showing how to store an image using a quantum system as well as some of the unique properties of that storage process derived from quantum mechanics laws.
The concept of quantum computing has arisen as a methodology by which very rapid computations can be achieved. There also has been considerable discussion about physical implementation's of the qubit. This has led...
详细信息
ISBN:
(纸本)081944975X
The concept of quantum computing has arisen as a methodology by which very rapid computations can be achieved. There also has been considerable discussion about physical implementation's of the qubit. This has led, in recent years, to a situation in which quantum computing and quantuminformation theory are being rapidly developed. In general, the specific advantages offered by quantum computing have been somewhat, nebulous. On the one hand, faster computing was promised, but we now know that no speedup of most algorithms exists relative the speed that can be obtained with massive parallel processing. Then, we are promised that the use of entanglement will make quantum computing possible with a much smaller use of resources. Yet, entanglement must be viewed as a hidden variable, which is not accessible in experiment. How does this provide the speedup? We have suggested that analog processing may provide a suitable alternative, and may be the basis which provides the speedup in quantum computing, but this is a controversial assertion. In this talk, we will discuss these particular viewpoints, along with several approaches to a wave basis for (quantum) computing.
The complexity of quantum computation remains poorly understood. While physicists attempt to find ways to create quantum computers, we still do not have much evidence one way or the other as to how useful these machin...
The complexity of quantum computation remains poorly understood. While physicists attempt to find ways to create quantum computers, we still do not have much evidence one way or the other as to how useful these machines will be. The tools of computational complexity theory should come to bear on these important questions. quantum computing often scares away many potential researchers in computer science because of the apparent background need in quantum mechanics and the alien looking notation used in papers on the topic. This paper will give an overview of quantum computation from the point of view of a complexity theorist. We will see that one can think of BQP as yet another complexity class and study its power without focusing on the physical aspects behind it. (C) 2002 Published by Elsevier Science B.V.
In this paper we introduce quantum interactive proof systems, which are interactive proof systems in which the prover and verifier may perform quantum computations and exchange quantum messages. It is proved that ever...
In this paper we introduce quantum interactive proof systems, which are interactive proof systems in which the prover and verifier may perform quantum computations and exchange quantum messages. It is proved that every language in PSPACE has a quantum interactive proof system that requires a total of only three messages to be sent between the prover and verifier and has exponentially small (one-sided) probability of error. It follows that quantum interactive proof systems are strictly more powerful than classical interactive proof systems in the constant-round case unless the polynomial time hierarchy collapses to the second level. (C) 2002 Elsevier Science B.V. All rights reserved.
We show that, if time comes when quantumalgorithms can be used for universal parallel computation, the "quantum-parallel" computer hardware will most probably be a classical physical system corresponding to...
详细信息
ISBN:
(纸本)081944975X
We show that, if time comes when quantumalgorithms can be used for universal parallel computation, the "quantum-parallel" computer hardware will most probably be a classical physical system corresponding to a Hilbert space and the actual realization may be the combination of analog and digital circuits. We first point out the practical difficulties of universal quantum computing which may prohibit practical applications as universal computers. Then we show how to apply analog microelectronic circuits to realize the architecture, data processing and parallel computing abilities of quantum computing via Hilbert space computing with analog circuits. Such a Hilbert-space-analog (HSA) computer simulates the Hilbert space and its operators, and it is able to use and test quantumalgorithms developed for the real quantum computers. Such a computer would. be free of most of the practical difficulties of realizing and running a real quantum computer. This computer can be made universal. It is remarkable that by using the same numbers of transistors as in today's PCs, such a HSA computer can manipulate similar to10(7) analog numbers corresponding to similar to22 qubits, simultaneously, by quantum-parallel processing.
Evolutionary programming (EP) is an efficient algorithm in solving optimization problems, but the criterion EP is of torpid convergence. In this paper, a novel kind of algorithm, the quantum evolutionary programming-Q...
详细信息
ISBN:
(纸本)0769519571
Evolutionary programming (EP) is an efficient algorithm in solving optimization problems, but the criterion EP is of torpid convergence. In this paper, a novel kind of algorithm, the quantum evolutionary programming-QEP, is proposed based on the combination of quantum theory with evolutionary theory. It is a kind of evolutionary programming with the form of quantum chromosome, whose core lies on the concept and principles of quantum computing, such as quantum bit and superposition of states. Using quantum mutation, we can make full use of the information of the current best individual to perform the next search, so QEP has rapid convergence and global searching capacity. Some simulation experiments are also given to prove its superiority over its counterpart.
Simulating quantum computation on a classical computer is a difficult problem. The matrices representing quantum gates, and the vectors modeling qubit states grow exponentially with an increase in the number of qubits...
详细信息
Simulating quantum computation on a classical computer is a difficult problem. The matrices representing quantum gates, and the vectors modeling qubit states grow exponentially with an increase in the number of qubits. However, by using a novel data structure called the quantuminformation Decision Diagram (QuIDD) that exploits the structure of quantum operators, a useful subset of operator matrices and state vectors can be represented in a form that grows polynomially with the number of qubits. This subset contains, but is not limited to, any equal superposition of n qubits, any computational basis state, n-qubit Pauli matrices, and n-qubit Hadamard matrices. It does not, however, contain the discrete Fourier transform (employed in Shor's algorithm) and some oracles used in Grover's algorithm. We first introduce and motivate decision diagrams and QuIDDs. We then analyze the runtime and memory complexity of QuIDD operations. Finally, we empirically validate QuIDD-based simulation by means of a general-purpose quantum computing simulator QuIDDPro implemented in C++. We simulate various instances of Grover's algorithm with QuIDDPro, and the results demonstrate that QuIDDs asymptotically outperform all other known simulation techniques. Our simulations also show that well-known worst-case instances of classical searching can be circumvented in many specific cases by data compression techniques.
A framework to describe a broad class of physical operations (including unitary transformations, dissipation, noise, and measurement) in a quantum optics experiment is given. This framework provides a powerful tool fo...
详细信息
ISBN:
(纸本)0750309334
A framework to describe a broad class of physical operations (including unitary transformations, dissipation, noise, and measurement) in a quantum optics experiment is given. This framework provides a powerful tool for assessing the capabilities and limitations of performing quantuminformationprocessing tasks using current experimental techniques. The Gottesman-Knill theorem is generalized to the infinite-dimensional representations of the group stabilizer formalism and further generalized to include non-invertible semigroup transformations, providing a theorem for the efficient classical simulation of operations within this framework. As a result, we place powerful constraints on obtaining computational speedups using current techniques in quantum optics.
暂无评论