Abstract
We study a model of quantum computation based on the continuously parameterized yet finite-dimensional Hilbert space of a spin system. We explore the computational powers of this model by analyzing a pilot problem we refer to as the close Hadamard problem. We prove that the close Hadamard problem can be solved in the spin system model with arbitrarily small error probability in a constant number of oracle queries. We conclude that this model of quantum computation is suitable for solving certain types of problems. The model is effective for problems where symmetries between the structure of the information associated with the problem and the structure of the unitary operators employed in the quantum algorithm can be exploited.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
See, e.g., paragraph 6.1 in [23] for an introduction to information theoretic lower bounds.
References
Benioff, P.: Quantum mechanical models of Turing machines that dissipate no energy. Phys. Rev. Lett. 48, 1581–1585 (1982). doi:10.1103/PhysRevLett.48.1581
Feynman, R.P.: Simulating physics with computers. Int. J. Theor. Phys. 21, 467–488 (1982). doi:10.1007/BF02650179
Deutsch, D.: Quantum theory, the Church–Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A 400, 97–117 (1985). doi:10.1098/rspa.1985.0070
Adcock, M.R.A.: Continuous-Variable Quantum Computation of Oracle Decision Problems. Ph.D. thesis, University of Calgary, (2012). http://theses.ucalgary.ca/bitstream/11023/387/2/ucalgary_2012_adcock_mark
Leonhardt, U.: Measuring the Quantum State of Light. Cambridge University Press, Cambridge (1997)
Deutsch, D.: Quantum computational networks. Proc. R. Soc. Lond. A 425, 73–90 (1989). doi:10.1098/rspa.1989.0099
Nielsen, M.A.: Cluster-state quantum computation. Rep. Math. Phys. 57, 147–161 (2006). doi:10.1016/S0034-4877(06)80014-5
Perelomov, A.: Generalized Coherent States and Their Applications. Springer, New York (1972)
Arrechi, F.T., Courtens, E., Gilmore, R., Thomas, H.: Atomic coherent states in quantum optics. Phys. Rev. A 6, 2211–2237 (1972). doi:10.1103/PhysRevA.6.2211
Radcliffe, J.M.: Some properties of coherent spin states. J. Phys. A Gen. Phys. 4, 313 (1971). doi:10.1088/0305-4470/4/3/009
Kitagawa, M., Ueda, M.: Squeezed spin states. Phys. Rev. A 47, 5138–5143 (1993). doi:10.1103/PhysRevA.47.5138
Adcock, M.R.A., Høyer, P., Sanders, B.C.: Limitations on continuous variable quantum algorithms with Fourier transforms. New J. Phys. 11, 103035 (2009). doi:10.1088/1367-2630/11/10/103035
Adcock, M.R.A., Høyer, P., Sanders, B.C.: Gaussian quantum computation with oracle-decision problems. Quantum Inf. Process. 12, 1759–1779 (2012). doi:10.1007/s11128-012-0489-1
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. North Holland, New York (1977)
Horadam, K.J.: Hadamard Matrices and Their Applications. Princeton University Press, Princeton (2007)
Bernstein, E., Vazirani, U.: Quantum Complexity Theory. In: Proceedings of the Twenty-fifth Annual Association for Computing Machinery Symposium on Theory of Computing, pp. 11–20. (1993). doi:10.1145/167088.167097
Mosca, M.: Quantum Computer Algorithms, Ph.D. thesis, University of Oxford, (1999). http://www.iqc.ca/~mmosca/web/papers/moscathesis
Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A 439, 553–558 (1992). doi:10.1098/rspa.1992.0167
Braunstein, S.L., Pati, A.K. (eds.): Quantum Information with Continuous Variables. Kluwer, Dordrecht (2003)
Hall, M.: Semi-automorphisms of Hadamard matrices. Math. Proc. Camb. Philos. Soc 77, 459–473 (1975). doi:10.1017/S0305004100051288
Michelson, A.M., Levesque, A.H.: Error Control Techniques for Digital Communication. Wiley, New York (1985)
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
Atallah, M.J.: Algorithms and Theory of Computation Handbook. CRC Press LLC, Boca Raton (1998)
Jin, W. L.: Dynamical Analysis of Grover’s Search Algorithm in Arbitrarily High-Dimensional Search Spaces, (2015). http://vixra.org/abs/1506.0069
Acknowledgments
We appreciate financial support from the Alberta Ingenuity Fund (AIF), Alberta Innovates Technology Futures (AITF), Canada’s Natural Sciences and Engineering Research Council (NSERC), the Canadian Network Centres of Excellence for Mathematics of Information Technology and Complex Systems (MITACS), and the Canadian Institute for Advanced Research (CIFAR).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Adcock, M.R.A., Høyer, P. & Sanders, B.C. Quantum computation with coherent spin states and the close Hadamard problem. Quantum Inf Process 15, 1361–1386 (2016). https://doi.org/10.1007/s11128-015-1229-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11128-015-1229-0