Determination of the quantum nature of correlations between two spatially separated systems plays a crucial role in quantum information science. Of particular interest is the questions of if and how these correlations enable quantum information protocols to be more powerful. Here, we report on a distributed quantum computation protocol in which the input and output quantum states are considered to be classically correlated in quantum informatics. Nevertheless, we show that the correlations between the outcomes of the measurements on the output state cannot be efficiently simulated using classical algorithms. Crucially, at the same time, local measurement outcomes can be efficiently simulated on classical computers. We show that the only known classicality criterion violated by the input and output states in our protocol is the one used in quantum optics, namely, phase-space nonclassicality. As a result, we argue that the global phase-space nonclassicality inherent within the output state of our protocol represents true quantum correlations.Introduction.-Correlations play an undeniable role in our understanding of the physical world. In our macroscopic classical description of commonplace phenomena, classical physics and classical information theory are in perfect agreement in characterization and quantification of correlated events. At a microscopic level, where quantum theory is our best candidate for explaining phenomena, however, the situation is different. Our informational inspections of a quantum world, i.e., quantum information theory, is based on our intuition from classical information theory and classical probability theory, mostly the notion of quantum entropy [1, 2]. However, a discrepancy emerges when physical constraints are taken into account to distinguish between quantum physics and classical physics, hence splitting quantum information approach to correlations from that of quantum optics.In quantum optics it is common to study nonclassical features of bosonic systems in a quantum analogue of the classical phase space [3]. While in a classical statistical theory in phase-space the state of the system is represented by a probability distribution, the quantum phase-space distributions can have negative regions, and hence, fail to be legitimate probability distributions [4]. The negativities are thus considered as nonclassicality signatures. Within multipartite quantum states, the phase-space nonclassicality is tempted to be interpreted as quantum correlations, due to the fact that in a classical description of the joint system no such effects are present [5,6].The sharpest contrast between the definition of quantum correlations in quantum information science and that of quantum optics has been demonstrated very recently by Ferraro and Paris [7]. They showed that the two definitions from quantum information and quantum optics are maximally inequivalent, meaning that every quantum state which is classically correlated with respect to the quantum information definition of quantum correlations is nece...